← 返回题目列表

Codeforces · 962/G

G. 可见黑色区域

中文机器翻译题面 查看原题

Petya 有一个由 $$$n$$$ 个顶点组成的多边形。 Petya多边形的所有边都与坐标轴平行,并且Petya多边形的每两个相邻边都互相垂直。保证多边形是简单的,即没有自交和自接触。 Petya 将多边形的所有内部区域(不包括边界)涂成黑色。

此外,Petya 有一个由其坐标定义的矩形窗口,通过该窗口他可以查看多边形。矩形窗口不能移动。矩形窗口的边与坐标轴平行。

蓝色代表多边形的边界,红色是Petya的窗口。本例的答案是 2。

确定Petya多边形的黑色连通区域的数量,可以通过矩形窗口看到。

输入

第一行包含四个整数 $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 < x_2$$$, $$$y_2 < y_1$$$) — 矩形窗口的左上角和右下角的坐标。

第二行包含一个整数 $$$n$$$ ($$$4 \le n \le 15\,000$$$) — Petya 多边形中的顶点数。

以下 $$$n$$$ 行中的每一行都包含两个整数 - Petya 多边形的顶点坐标(按逆时针顺序排列)。保证给定的多边形满足语句中描述的条件。

矩形窗口的所有坐标和多边形顶点的所有坐标均为非负且不超过$$$15\,000$$$。

输出

打印Petya多边形的黑色连通区域的数量,通过矩形窗口可以看到。

示例

输入 #1

5 7 16 3
16
0 0
18 0
18 6
16 6
16 1
10 1
10 4
7 4
7 2
2 2
2 6
12 6
12 12
10 12
10 8
0 8

输出 #1

2

注意

该示例对应于上图。