#P18803. [POI1998] 窗口
[POI1998] 窗口
[POI1998] 窗口
题目描述
平面上有一个简单多边形,它的边都平行于坐标轴,任意两条相邻边互相垂直,所有顶点的坐标均为整数。
多边形的内部被涂成红色,边界没有涂色。另有一个边平行于坐标轴的矩形窗口。
透过这个窗口,可以看到多边形内部的一些红色区域。求这些红色区域共有多少个连通块。只在边界或单个点处接触的区域不因此连通。
窗口边界可以与多边形的边重合,也可以经过多边形的顶点。
输入格式
第一行四个整数 ,分别表示窗口的左上角和右下角。满足 ,。
第二行一个整数 ,。
接下来 行,每行两个整数,表示多边形的一个顶点。顶点按逆时针顺序给出;沿这个顺序走过多边形边界时,多边形内部位于左侧。
输入中所有坐标均在 内。最后一个顶点与第一个顶点之间也有一条边。
输出格式
输出一个整数,表示窗口中可见红色区域的连通块数。若看不到红色区域,输出 。
样例输入
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