P6886 [COCI 2016/2017 #3] 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$ 种。
#### 样例 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