Problem1159--#6049. 「雅礼集训 2017 Day10」拍苍蝇

1159: #6049. 「雅礼集训 2017 Day10」拍苍蝇

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

有一天,小 A 的母亲对他家里的卫生状况非常不满意,他的房间里有非常多的苍蝇。在母亲的威逼利诱下,小 A 拿起了苍蝇拍去消灭家里的苍蝇。然而,小 A 以前从来没有亲手消灭过任何一只苍蝇,以至于在他拿起苍蝇拍的那一刻,他对苍蝇起了怜悯之心 —— 他不想伤害任何一只苍蝇。现在,小 A 面前的窗户上有 N N N 只苍蝇,他想知道有多少种方式可以在他拿起苍蝇拍拍窗户的时候,不伤害任何一只苍蝇。

窗户可以看作是一个左下角位于坐标系原点的矩形,苍蝇拍可以看作是一个多边形。在小 A 向窗户挥苍蝇拍时,对应多边形的顶点必须位于坐标系的整点上,并且苍蝇拍所在位置不能超过窗户所在范围。一只苍蝇会被伤害当且仅当小 A 用苍蝇拍拍向窗户时,苍蝇位于苍蝇拍内部、边上或顶点上。

输入格式

第一行三个正整数 Xp X_p XpYp Y_p YpN N N,分别表示窗户右上角的坐标和窗户上苍蝇的数量。
接下来 N N N 行每行两个整数 X X XY Y Y,表示苍蝇在窗户上的位置。
接下来一行一个正整数 K K K,表示苍蝇拍的顶点数。
最后 K K K 行每行两个正整数 Xi X_i XiYi Y_i Yi,表示苍蝇拍上的第 i i i 个顶点。按顶点给出的顺序,连接相邻的顶点(首尾相连),即为苍蝇拍外轮廓。

输出格式

输出仅一个正整数,表示苍蝇拍挥向窗户不伤害一只苍蝇的方案数。

样例

样例输入 1

4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2

样例输出 1

4

样例输入 2

5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6

样例输出 2

3

样例输入 3

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

样例输出 3

1

数据范围与提示

对于 70% 70\% 70% 的数据,1≤Xp,Yp≤100 1 \leq X_p, Y_p \leq 100 1Xp,Yp100
对于 100% 100\% 100% 的数据,1≤Xp,Yp≤500,0≤N≤Xp×Yp,3≤K≤100000,−109≤Xi,Yi≤109 1 \leq X_p, Y_p \leq 500, 0 \leq N \leq X_p \times Y_p, 3 \leq K \leq 100000, -10 ^ 9 \leq X_i, Y_i \leq 10 ^ 9 1Xp,Yp500,0NXp×Yp,3K100000,109Xi,Yi109

Source/Category