LOJ#6049. 「雅礼集训 2017 Day10」拍苍蝇（计算几何+bitset）

逃离我推掉我的手 2021-12-23 05:47 215阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

首先可以用一个矩形去套这个多边形，那么我们只要枚举这个矩形的左下角就可以枚举完所有多边形的位置了

我们先对每一个\\(x\\)坐标开一个\\(bitset\\)，表示这个\\(x\\)坐标里哪些\\(y\\)坐标处有苍蝇。然后再处理出矩形中哪些位置会被覆盖，这个同样可以枚举\\(x\\)坐标，然后对于所有线段，如果它穿过这个\\(x\\)坐标，就用一个\\(stack\\)存起来，然后把所有\\(stack\\)里的\\(sort\\)一下，乱搞就好了（具体可以看代码）

注意只有一条线段完全穿过\\(x\\)才有可能会产生一个区间覆盖的效果。还有一种情况就是两条线段加起来穿过\\(x\\)，然而这两条线段公共端点在\\(x\\)轴上，那么之前是不会判的，所以要特判

听说这题还有\\(FFT\\)的做法……话说那些大爷们真的是在做计蒜几盒么……

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define inf 0x3f3f3f3f
    #define inline __inline__ __attribute__((always_inline))
    #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
    #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
    template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    const int N=505,M=1e5+5;
    struct node{int x,y;}p[M],nfly,a,b;
    inline void swap(node &a,node &b){node t=a;a=b,b=t;}
    bitset<N>pfly[N],fly[N],now;double st[N];bool ans[N][N];
    int n,m,k,top,mnx=inf,mny=inf,mxx=-inf,mxy=-inf,res;
    int main(){
    //  freopen("testdata.in","r",stdin);
        n=read(),m=read(),k=read();
        fp(i,1,k)nfly.x=read(),nfly.y=read(),fly[nfly.x].set(nfly.y);
        k=read();
        fp(i,1,k){
            p[i].x=read(),p[i].y=read();
            cmin(mnx,p[i].x),cmin(mny,p[i].y),cmax(mxx,p[i].x),cmax(mxy,p[i].y);
        }
        mxx-=mnx,mxy-=mny;fp(i,1,k)p[i].x-=mnx,p[i].y-=mny,pfly[p[i].x].set(p[i].y);
        fp(x,0,mxx){
            top=0;
            fp(i,1,k){
                a=p[i],b=p[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){
                    fp(y,a.y+1,b.y-1)pfly[x].set(y);
                    continue;
                }
                double k=1.0*(b.y-a.y)/(b.x-a.x);
                st[++top]=k*(x-a.x)+a.y;
            }
            sort(st+1,st+1+top);
            for(R int y=0,flag=0,i=1;y<=mxy;++y){
                while(i<=top&&st[i]<y)++i,flag^=1;
                if(flag||(i<=top&&st[i]==y))pfly[x].set(y);
            }
        }
        fp(i,0,mxx)fp(y,0,m-mxy){
            now=pfly[i]<<y;
            fp(x,0,n-mxx)if(!ans[x][y]&&(now&fly[x+i]).any())ans[x][y]=1;
        }
        fp(x,0,n-mxx)fp(y,0,m-mxy)res+=!ans[x][y];
        printf("%d\n",res);
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10712585.html

[Link 1]: https://loj.ac/problem/6049