1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
| #include<bits/stdc++.h> using namespace std; typedef long long ll; #define reg register #define Mod1(x) ((x>=P)&&(x-=P)) #define Mod2(x) ((x<0)&&(x+=P)) #define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i) template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); } char IO; int rd(){ int s=0,f=0; while(!isdigit(IO=getchar())) if(IO=='-') f=1; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; } const int N=510,M=10010,P=998244353; const double eps=1e-9; int X,Y,D,n,m; struct Point{ int x,y; void Read(){ x=rd(), y=rd(); } } A[M]; const int K=N*N*4.2; int F[K],G[K]; double U[M]; int cnt,rev[K]; ll qpow(ll x,ll k=P-2) { ll res=1; for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P; return res; } void NTT(int n,int *a,int f){ static int e[K>>1]; rep(i,1,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]); e[0]=1; for(int i=1;i<n;i<<=1) { int w=qpow(f==1?3:(P+1)/3,(P-1)/i/2); for(int j=i-2;j>=0;j-=2) e[j+1]=1ll*(e[j]=e[j>>1])*w%P; for(int l=0;l<n;l+=i*2) { for(int j=l;j<l+i;++j) { int t=1ll*a[j+i]*e[j-l]%P; a[j+i]=a[j]-t,Mod2(a[j+i]); a[j]+=t,Mod1(a[j]); } } } if(f==-1) { ll base=qpow(n); rep(i,0,n-1) a[i]=a[i]*base%P; } } void Cover(int x,int y){ F[(X+1-x)*D+Y-y]=1; } int main(){ X=rd(),Y=rd(),D=Y+2; rep(i,1,n=rd()) { int x=rd(),y=rd(); G[x*D+y]=1; } int mix=1e9,miy=1e9,max=-1e9,may=-1e9; rep(i,1,m=rd()) { A[i].Read(); cmin(mix,A[i].x),cmax(max,A[i].x); cmin(miy,A[i].y),cmax(may,A[i].y); } max-=mix,may-=miy; if(max>X || may>Y) return puts("0"),0; rep(i,1,m) A[i].x-=mix,A[i].y-=miy; A[m+1]=A[1]; rep(i,0,X) { cnt=0; rep(j,1,m) { Point L=A[j],R=A[j+1]; if(L.x>R.x) swap(L,R); if(i<L.x || i>R.x) continue; if(L.x==R.x) { rep(y,min(L.y,R.y),::max(L.y,R.y)) Cover(i,y); continue; } double y=1.0*(R.y-L.y)/(R.x-L.x)*(i-L.x)+L.y; if(i<R.x) U[++cnt]=y; if(abs(y-int(y))<eps) Cover(i,y); } sort(U+1,U+cnt+1); for(int j=1;j<=cnt;j+=2) for(int y=ceil(U[j]);y<=U[j+1]+eps;++y) Cover(i,y); } int R=1,cc=-1; while(R<=(X+1)*2*D) R<<=1,cc++; rep(i,1,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<cc); NTT(R,F,1),NTT(R,G,1); rep(i,0,R-1) F[i]=1ll*F[i]*G[i]%P; NTT(R,F,-1); int ans=0; rep(i,0,X-max) rep(j,0,Y-may) if(!F[(X+1+i)*D+Y+j]) ans++; printf("%d\n",ans); }
|