Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB

#334. Meksikanac

统计

题目描述

Norman 有一个给定的$K$边形的苍蝇拍。他想知道有多少种放置苍蝇拍的方法,使得这个苍蝇拍的顶点在顶点为$(0,0)$和$(X_p,Y_p)$的矩形中,并且各个顶点是整点,满足没有一个苍蝇被伤害。

其中,整点的定义是横坐标和纵坐标都是整数的点。

这个矩形中有$N$个苍蝇,每一个苍蝇可以看成一个点$(X,Y)$。一个苍蝇会被伤害,当且仅当这个苍蝇在这个苍蝇拍的顶点,边或内部。

输入输出格式

输入格式

第一行包含三个正整数$X_p,Y_p,N$,意义同上。

以下$N$行,每行包含两个正整数$(X,Y)$,表示第$i$个苍蝇的坐标。

接下来一行有一个正整数$K$表示多边形的点数。

以下$K$行,每行两个正整数$(X_i,Y_i)$,表示当苍蝇拍的第一个顶点的坐标为$(X_1,Y_1)$的时候,其他顶点的坐标。各个顶点是顺次给出的。

输出格式

你需要输出有多少可行的放置苍蝇拍的方案。

输入输出样例

输入样例 #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
4 1
5 3
7 4
5 5
4 7
3 5

输出样例 #3

1

说明/提示

样例解释

样例 1 解释

可以放置的苍蝇拍的位置如下:

共$4$种。

样例 2 解释

可以放置的苍蝇拍的位置如下:

共$3$种。

样例 3 解释

可以放置的苍蝇拍的位置如下:

共$1$种。

数据规模与约定

对于$63\%$的数据,满足$1\le X_p,Y_p\le100$。

对于$100\%$的数据,满足$1\le X_p,Y_p\le500,1\le N\le X_p \times Y_p,3\le K\le10^4,0< X< X_p,0< Y< Y_p,-10^9\le X_i,Y_i\le10^9$。