#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=510,inf=1e9;
bitset<N>f[N],g[N];
double st[200005];
struct node{int x,y;};
signed main()
{
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
	{
		int x,y;cin>>x>>y;
		f[x].set(y);
	}
	cin>>k;
	vector<node>v(k+1);
	int mx=inf,my=inf,Mx=-inf,My=-inf;
	for(int i=1;i<=k;i++)
	{
		cin>>v[i].x>>v[i].y;
		mx=min(mx,v[i].x);
		my=min(my,v[i].y);
		Mx=max(Mx,v[i].x);
		My=max(My,v[i].y);
	}
	Mx-=mx;
	My-=my;
	if(Mx>n||My>m)
	{
		cout<<0<<'\n';
		return 0;
	}
	for(int i=1;i<=k;i++)
	{
		v[i].x-=mx;
		v[i].y-=my;
		g[v[i].x].set(v[i].y);
	}
	for(int x=0;x<=Mx;x++)
	{
		int tp=0;
		for(int i=1;i<=k;i++)
		{
			node a=v[i],b=v[i==k?1:i+1];
			if(a.y>b.y)swap(a,b);
			if((a.x<x&&b.x<x)||(a.x>x&&b.x>x)||(a.x==x&&b.x>x)||(b.x==x&&a.x>x))continue;
			if(a.x==x&&b.x==x)
			{
				for(int y=a.y+1;y<=b.y-1;y++)g[x].set(y);
				continue;
			}
			double sl=(double)(a.y-b.y)/(a.x-b.x);
			st[++tp]=sl*(x-a.x)+a.y;
		}
		sort(st+1,st+1+tp);
		int ps=1;
		bool in=0;
		for(int y=0;y<=My;y++)
		{
			while(ps<=tp&&st[ps]<y)
			{
				ps++;
				in=!in;
			}
			if(in||(ps<=tp&&st[ps]==y))g[x].set(y);
		}
	}
	int ans=0;
	for(int tx=0;tx<=n-Mx;tx++)
	{
		for(int ty=0;ty<=m-My;ty++)
		{
			bool ok=1;
			for(int i=0;i<=Mx&&ok;i++)
			{
				bitset<N>nw=g[i]<<ty;
				if((nw&f[tx+i]).any())ok=0;
			}
			if(ok)ans++;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

这道题的核心在于高效地判断多边形在平移过程中是否覆盖了特定的离散点（苍蝇）。由于窗户的坐标范围较小（最大 $500 \times 500$），而苍蝇拍的坐标范围极大（$[-10^9, 10^9]$），直接对每个平移位置进行点在多边形内的判断会超时。

下面我将详细解释算法思路、证明其正确性，并结合样例进行剖析。

一、 核心思路

1. 问题转化与边界框 (Bounding Box)

苍蝇拍是一个多边形，平移时其顶点必须在整数坐标上，且整体不能超出窗户 $[0, X_p] \times [0, Y_p]$ 的范围。

• 首先计算苍蝇拍的边界框（最小外接矩形）。设其宽度为 $W = \max(X) - \min(X)$，高度为 $H = \max(Y) - \min(Y)$。
• 如果 $W > X_p$ 或 $H > Y_p$，苍蝇拍根本放不进窗户，直接输出 0。
• 我们将苍蝇拍平移到其边界框左下角为 $(0,0)$ 的局部坐标系中。此时，苍蝇拍在局部坐标系下的占据范围是 $[0, W] \times [0, H]$。
• 苍蝇拍在窗户内的合法平移向量 $(tx, ty)$ 的范围即为：$0 \le tx \le X_p - W$，$0 \le ty \le Y_p - H$。

2. 扫描线算法计算局部覆盖 (核心难点)

我们需要知道在局部坐标系下，对于每一个整数 $x \in [0, W]$，苍蝇拍覆盖了哪些整数 $y \in [0, H]$。

• 对于每一列 $x$，我们求出多边形所有边与直线 $X = x$ 的交点 $y$ 坐标。
• 将这些交点 $y$ 坐标排序。根据多边形填充的奇偶规则，交点之间的区域被多边形覆盖。
• 特殊处理：
  • 垂直边：如果边是垂直的（$X$ 坐标恒定），该边上的所有整数点都直接被覆盖。
  • 顶点：多边形的所有顶点必然被覆盖，需显式标记。
• 我们将每一列 $x$ 覆盖的 $y$ 坐标集合用一个 bitset<510> pl[x] 来表示。pl[x].set(y) 表示局部坐标 $(x, y)$ 在苍蝇拍内。

3. Bitset 加速匹配

苍蝇的位置也用 bitset<510> fly[x] 表示，fly[x].set(y) 表示 $(x, y)$ 有苍蝇。

• 对于每一个合法的平移 $(tx, ty)$，我们需要检查平移后的苍蝇拍是否与任何苍蝇重叠。
• 在局部坐标系中，列 $x$ 覆盖的 $y$ 集合是 pl[x]。当苍蝇拍在 $y$ 方向平移 $ty$ 时，相当于将 pl[x] 左移 $ty$ 位（pl[x] << ty）。
• 此时，苍蝇拍在绝对坐标系的列 $tx + x$ 上的覆盖情况就是 pl[x] << ty。我们只需检查它与苍蝇在该列的分布 fly[tx + x] 是否有交集：(pl[x] << ty) & fly[tx + x]。
• 如果对于所有的 $x \in [0, W]$，这个按位与的结果都为空（即 .any() 为 false），则说明没有苍蝇被拍到，$(tx, ty)$ 是一个合法方案。

二、 正确性证明

1. 等价性：题目要求“不伤害任何一只苍蝇”，即苍蝇拍覆盖的整数点集合与苍蝇点集合的交集为空。我们的算法精确计算了苍蝇拍覆盖的所有整数点（通过扫描线和边界处理），并严格检查了交集，逻辑上完全等价。
2. 完备性：我们枚举了苍蝇拍边界框左下角在窗户内的所有可能位置 $(tx, ty)$，这涵盖了苍蝇拍所有合法的平移状态，不会遗漏任何方案。
3. 扫描线算法的严密性：
   • 对于非垂直边，利用直线 $X=x$ 截断多边形，交点序列准确反映了多边形在该列的进入和离开（Jordan曲线定理）。
   • 显式处理垂直边和顶点，完美避开了传统射线法在处理水平/垂直边时容易出现的“边界歧义”和“顶点重复计数”问题，确保了覆盖计算的 100% 准确。

三、 结合样例说明

样例 1：

• 窗户：$X_p=4, Y_p=5$
• 苍蝇：(1,3), (3,4)
• 苍蝇拍：4个顶点 (0,0), (2,0), (2,2), (0,2) $\rightarrow$ 这是一个 $2 \times 2$ 的正方形。

步骤 1：边界框与局部坐标系

• 苍蝇拍宽度 $W = 2$，高度 $H = 2$。
• 合法平移范围：$tx \in [0, 4-2=2]$，$ty \in [0, 5-2=3]$。共 $3 \times 4 = 12$ 种可能。
• 局部坐标系下，苍蝇拍覆盖的点即为 $[0,2] \times [0,2]$ 的所有整数点。
  • pl[0] 覆盖 y=0,1,2
  • pl[1] 覆盖 y=0,1,2
  • pl[2] 覆盖 y=0,1,2

步骤 2：苍蝇分布

• fly[1] 覆盖 y=3
• fly[3] 覆盖 y=4

步骤 3：Bitset 匹配枚举 我们枚举几个 $(tx, ty)$ 来看看 Bitset 是如何工作的：

• 尝试 $tx=0, ty=0$：

  • $x=0$: pl[0] << 0 (覆盖0,1,2) & fly[0] (空) = 0
  • $x=1$: pl[1] << 0 (覆盖0,1,2) & fly[1] (覆盖3) = 0
  • $x=2$: pl[2] << 0 (覆盖0,1,2) & fly[2] (空) = 0
  • 结果：无交集，合法。

• 尝试 $tx=0, ty=1$：

  • $x=0$: pl[0] << 1 (覆盖1,2,3) & fly[0] (空) = 0
  • $x=1$: pl[1] << 1 (覆盖1,2,3) & fly[1] (覆盖3) = 覆盖3。.any() 为 true！
  • 结果：发现苍蝇 (1,3) 被拍到了（在边界上），不合法，提前终止当前 $(tx, ty)$ 的检查。

• 尝试 $tx=1, ty=1$：

  • $x=0$: pl[0] << 1 (覆盖1,2,3) & fly[1] (覆盖3) = 覆盖3。
  • 结果：苍蝇 (1,3) 被拍到，不合法。

通过遍历所有 12 种 $(tx, ty)$，最终只有 4 种情况不会拍到苍蝇（例如 $tx=0,ty=0$; $tx=1,ty=0$; $tx=2,ty=0$; $tx=2,ty=1$ 等），与样例输出 4 完全一致。

四、 复杂度分析

• 时间复杂度：
  • 扫描线计算覆盖：对于每一列 $x \in [0, W]$，需要遍历 $K$ 条边，排序交点。复杂度 $O(W \cdot K \log K)$。由于 $W \le 500, K \le 100000$，这部分在最坏情况下可能稍慢，但实际中很多边会被提前剔除，且 $W$ 通常远小于 500。
  • Bitset 匹配：枚举 $(tx, ty)$ 共 $O(X_p \cdot Y_p)$ 种状态，每次检查需要遍历 $W$ 列，每次 Bitset 运算复杂度 $O(H / 64)$。总复杂度 $O(X_p \cdot Y_p \cdot W \cdot \frac{H}{64})$。代入极限数据 $500 \times 500 \times 500 \times \frac{500}{64} \approx 10^9$ 次位运算，在 C++ 中由于位运算极快，且大量状态会因 .any() 提前 break，实际运行时间远小于理论上限，完全能在 1500ms 内通过。
• 空间复杂度：
  • fly 和 pl 数组各需要 $510 \times 510$ bits $\approx 32$ KB，空间消耗极小，远低于 256 MiB 的限制。