「雅礼集训 2017 Day10」拍苍蝇

刺骨的言语ヽ痛彻心扉 2021-12-22 00:17 172阅读 0赞

## [ 传送门 ][Link 1] ##

## **Description**  ##

> 有一天，小 A 的母亲对他家里的卫生状况非常不满意，他的房间里有非常多的苍蝇。在母亲的威逼利诱下，小 A 拿起了苍蝇拍去消灭家里的苍蝇。然而，小 A 以前从来没有亲手消灭过任何一只苍蝇，以至于在他拿起苍蝇拍的那一刻，他对苍蝇起了怜悯之心 —— 他不想伤害任何一只苍蝇。现在，小 A 面前的窗户上有 只苍蝇，他想知道有多少种方式可以在他拿起苍蝇拍拍窗户的时候，不伤害任何一只苍蝇。
> 
> 窗户可以看作是一个左下角位于坐标系原点的矩形，苍蝇拍可以看作是一个多边形。在小 A 向窗户挥苍蝇拍时，对应多边形的顶点必须位于坐标系的整点上，并且苍蝇拍所在位置不能超过窗户所在范围。一只苍蝇会被伤害当且仅当小 A 用苍蝇拍拍向窗户时，苍蝇位于苍蝇拍内部、边上或顶点上。

## **Solution**  ##

> 和这场比赛的T3是类似的[sailing][]
> 
> 同样是处理出01序列，将其中一个反转用FFT卷积优化
> 
> 难度在于如何求出那些在多边形中的点
> 
> 显然一个一个点求太慢了
> 
> 所以考虑一列一列的求，事先先处理出与这一列相交的交点
> 
> 第\\(2n-1\\)到\\(2n\\)个交点内的点都是处于多边形的
> 
> 人形大常数，跑得还不如bitset快

## **Code ** ##

#include<bits/stdc++.h> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define ll long long #define db double #define reg register #define ri reg int i inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } const int NN=1<<19|5; const int MS=2.6e4,MN=505,inf=0x3f3f3f3f; const db eps=1e-12,Pi=std::acos(-1.); struct Node{int x,y;}S[MS],T[MS]; int Xp,Yp,N,K,ans; db P[MS]; bool _S[MN][MN],_T[MN][MN]; struct complex { double x,y; complex(double x=0,double y=0):x(x),y(y){} inline complex operator+(const complex& o)const{return complex(x+o.x,y+o.y);} inline complex operator-(const complex& o)const{return complex(x-o.x,y-o.y);} inline complex operator*(const complex& o)const{return complex(x*o.x-y*o.y,x*o.y+y*o.x);} inline void swap(complex& o){register complex t=o;o=(*this);*this=t;} }a[NN],b[NN]; int Nn,di,pos[NN]; inline void FFT(complex *a,int type) { register int i,j,p,k; for(i=0;i<Nn;++i)if(i<pos[i])a[i].swap(a[pos[i]]); for(i=1;i<Nn;i<<=1) { complex wn(cos(Pi/i),type*sin(Pi/i)); for(p=i<<1,j=0;j<Nn;j+=p) { complex w(1,0); for(k=0;k<i;++k,w=w*wn) { complex X=a[j+k],Y=w*a[j+i+k]; a[j+k]=X+Y;a[j+i+k]=X-Y; } } } } inline void combine(complex *a,complex *b,int n,int m) { for(Nn=1;Nn<=n+m;Nn<<=1,di++); for(ri=0;i<Nn;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(di-1)); FFT(a,1);FFT(b,1);for(ri=0;i<Nn;++i)a[i]=a[i]*b[i];FFT(a,-1); } int main() { #ifdef PAC freopen("fly4.in","r",stdin); freopen("fly4.out","w",stdout); #endif int xi=inf,yi=inf,xx=-inf,yx=-inf,lenx,leny,tt; reg int i,j,x,y; Xp=read();Yp=read();N=read(); for(i=1;i<=N;++i) _S[S[i].x=read()][S[i].y=read()]=1; K=read(); for(i=1;i<=K;++i) { T[i].x=read();T[i].y=read(); xi=min(xi,T[i].x);xx=max(xx,T[i].x); yi=min(yi,T[i].y);yx=max(yx,T[i].y); } lenx=xx-xi;leny=yx-yi; if(lenx>Xp||leny>Yp) return 0*puts("0"); for(i=1;i<=K;++i) _T[T[i].x-=xi][T[i].y-=yi]=1; for(x=0;x<=lenx;++x) { tt=0;memset(P,0,sizeof P);P[0]=-inf; for(i=1;i<=K;++i) { Node a=T[i],b=T[i%K+1];if(a.y>b.y) std::swap(a,b); if(a.x==x&&b.x==x)for(y=a.y;y<=b.y;++y) _T[x][y]=1; else if((a.x-x)*(b.x-x)<=0&&!(a.x==x&&b.x>x)&&!(b.x==x&&a.x>x)) P[++tt]=(db)(x-a.x)*(db)(a.y-b.y)/(db)(a.x-b.x)+(db)a.y; } std::sort(P+1,P+tt+1); for(i=0,y=0;y<=leny;_T[x][y]|=((i^((~i&1)&&y-P[i]<eps))&1),++y)while(i+1<=tt&&(db)y>=P[i+1])++i; } for(i=0;i<=Xp;++i)for(j=0;j<=Yp;++j)a[i*(Yp+1)+j].x=_S[i][j]?1.:0.; int LEN1=(Xp+1)*(Yp+1),LEN2=0; for(i=0;i<=lenx;++i) { for(j=0;j<=leny;++j)b[LEN2++].x=_T[i][j]?1.:0.; if(i!=lenx) for(j=leny+1;j<=Yp;++j) b[LEN2++].x=0.; } std::reverse(b,b+LEN2); combine(a,b,LEN1,LEN2); for(i=0;i<=Xp-lenx;++i)for(j=0;j<=Yp-leny;++j) if(((int)(a[LEN2+(i*(Yp+1)+j)-1].x/Nn+.5))==0) ++ans; printf("%d\n",ans); return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10671570.html

[Link 1]: https://loj.ac/problem/6049
[sailing]: https://www.cnblogs.com/PaperCloud/p/FCS_noi2019_day1.html