#P18803. [POI1998] 窗口

[POI1998] 窗口

[POI1998] 窗口

题目描述

平面上有一个简单多边形,它的边都平行于坐标轴,任意两条相邻边互相垂直,所有顶点的坐标均为整数。

多边形的内部被涂成红色,边界没有涂色。另有一个边平行于坐标轴的矩形窗口。

透过这个窗口,可以看到多边形内部的一些红色区域。求这些红色区域共有多少个连通块。只在边界或单个点处接触的区域不因此连通。

窗口边界可以与多边形的边重合,也可以经过多边形的顶点。

输入格式

第一行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,分别表示窗口的左上角和右下角。满足 x1<x2x_1<x_2,y2<y1y_2<y_1。

第二行一个整数 nn,4≤n≤50004\le n\le5000。

接下来 nn 行,每行两个整数,表示多边形的一个顶点。顶点按逆时针顺序给出;沿这个顺序走过多边形边界时,多边形内部位于左侧。

输入中所有坐标均在 [0,10000][0,10000] 内。最后一个顶点与第一个顶点之间也有一条边。

输出格式

输出一个整数,表示窗口中可见红色区域的连通块数。若看不到红色区域,输出 00。

样例输入

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