[POI1998]窗户

Grade 0 Open Time Tuesday, 22 January 2013, 9:55 am
Discount 0.8 Time Discount Tuesday, 22 January 2013, 9:55 am
Allow late Yes Close Time Tuesday, 22 January 2013, 9:55 am
Input file okn.in Output file okn.out

我们在笛卡尔坐标系中有一个多边形,多边形的边平行于坐标轴,每两条相邻的边是垂直正交的并且每一个顶点的坐标都是整数。我们还给出一个边也平行于坐标轴的矩形窗户。多边形的内部被涂成红色,那么有几个分开的红色部分将在窗户中被看到。

例子:

如下图:

Image:Okn.png

有两个红色的部分将被通过窗子看到。

任务:

写一个程序

  • 从文件中读入窗户与多边形的描述。

  • 计算能通过窗户看到的分开的红色部分的个数。

  • 将结果写入文件。

输入:

在文件的第一行有四个整数x1,y1,x2,y2 (0<=x1,y1,x2,y2<=10000),有一个空格隔开,(x1,y1)是窗户左上角的坐标,(x2,y2)是窗户右下角的坐标。 下一行有一个整数n(4<=n<=5000)表示多边形的顶点数。以下n行以逆时针的顺序给出了多边形的顶点坐标,也就是说当我们沿着给出的 多边形的边走时,多边形的内部在外部的左边。每一行包括两个整数x y(0<=x,y<=10000),有一个空格隔开,第(i+2)行表示多边形的第i个顶点。

输出:

在文件的第一行有且仅有一个整数表示能够通过窗户看到的分开的红色区域的个数。

输入样例:

0 5 8 1
24
0 0
4 0
4 2
5 2
5 0
7 0
7 3
3 3
3 2
2 2
2 4
1 4
1 5
2 5
2 6
3 6
3 5
4 5
4 6
5 6
5 4
7 4
7 7
0 7

输出样例:

2