【JZOJ5017】拍苍蝇 题解

题目大意

  平面大小为 $Xp \cdot Yp$，上面有 n 只苍蝇，每只坐标为 (xi, yi)。
  然后给出一个 $k$ 个顶点的多边形（可能为凹），你要将多边形放在平面上，规定顶点必须在整点上，且不能有苍蝇在多边形内或多边形上。
  求方案数。
  $Xp, Yp \le 500， n \le Xp \cdot Yp$
  $k \le 10^4$
  小测试点 1.5s，大测试点 3s。

答案为 1 的样例

题解

  我们把每一行看作是 01 序列，有苍蝇就是 1，没有就是 0。
  然后把多边形也看作是 01 矩阵，被多边形覆盖的就是 1，否则是 0。
  （求这个可以枚举每个点是否在多边形内（射线法），也可以基于此用类似前缀和的方法（我把每条边上方最近的整点打标记，然后从底向上前缀异或和，就知道每个点是在内还是外了，然后特殊处理边上的点））

解法1

  有了上述方法之后我们就可以用 bitset 把这些东西存下来，然后暴力枚举多边形放哪，再用 bitset 判断。
  由于状态是不满的，所以可以过。

解法2（标算）

  把这些看成 01 序列（或矩阵）的话，就可以用 FFT 来代替 bitset 了。。。
  貌似是二维的 FFT，操作难度有点大。。。

解法1代码

#include<cstdio>
#include<algorithm>
#include<bitset>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=250005, maxk=1e4+5, maxp=505;
const int inf=2147483647;

int xp,yp,kx,ky,n,k,X[maxk],Y[maxk],ex1[maxk],ex2[maxk],ey1[maxk],ey2[maxk];
bitset<maxp> mp[maxp],fp[maxp];

bitset<maxp> zero;
bool bz[maxp][maxp];
int main()
{
	scanf("%d %d %d",&xp,&yp,&n);
	fo(i,1,n)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		mp[x][y]=1;
	}
	
	scanf("%d",&k);
	kx=ky=inf;
	fo(i,1,k)
	{
		scanf("%d %d",&X[i],&Y[i]);
		kx=min(kx,X[i]), ky=min(ky,Y[i]);
	}
	fo(i,1,k) X[i]-=kx, Y[i]-=ky;
	kx=ky=0;
	fo(i,1,k)
	{
		kx=max(kx,X[i]), ky=max(ky,Y[i]);
		if (X[i]>xp || Y[i]>yp) {printf("0\n"); return 0;}
	}
	
	fo(i,1,k)
	{
		ex1[i]=X[i], ey1[i]=Y[i];
		int t=(i%k)+1;
		ex2[i]=X[t], ey2[i]=Y[t];
		if (ex1[i]>ex2[i]) swap(ex1[i],ex2[i]), swap(ey1[i],ey2[i]);
		if (ex1[i]==ex2[i] && ey1[i]>ey2[i]) swap(ey1[i],ey2[i]);
	}
	fo(i,1,k) if (ex1[i]!=ex2[i])
	{
		int ad=(ey1[i]<ey2[i]) ?1 :-1;
		int y=ey1[i];
		fo(x,ex1[i],ex2[i])
		{
			if (ad==1)
			{
				while ((LL)(y-ey1[i])*(ex2[i]-x)<(LL)(ey2[i]-y)*(x-ex1[i])) y+=ad;
			} else
			{
				while (x>ex1[i] && (LL)((y+ad)-ey1[i])*(ex2[i]-x)>=(LL)(ey2[i]-(y+ad))*(x-ex1[i])) y+=ad;
			}
			if ((LL)(y-ey1[i])*(ex2[i]-x)==(LL)(ey2[i]-y)*(x-ex1[i])) bz[x][y]=1;
			if (x<ex2[i] && y<=ky) fp[x][y]=(fp[x][y]) ?0 :1 ;
		}
	}
	fo(i,0,kx)
		fo(j,1,ky) fp[i][j]=fp[i][j]^fp[i][j-1];
	fo(i,0,kx)
		fo(j,0,ky) if (bz[i][j]) fp[i][j]=1;
	fo(i,1,k) if (ex1[i]==ex2[i])
		fo(j,ey1[i],ey2[i]) fp[ex1[i]][j]=1;
	
	int ans=0;
	fo(x,0,xp-kx)
		fo(y,0,yp-ky)
		{
			bitset<maxp> ans1=zero;
			fo(i,0,kx) ans1|=mp[x+i]&(fp[i]<<y);
			ans+=(!ans1.any());
		}
	
	printf("%d\n",ans);
}