1 条题解

  • 0
    @ 2025-9-10 9:07:16

    C++ :

    #include<bits/stdc++.h>
    const int N=1600007;
    char buf[30000007],*ptr=buf-1;
    int _(){
        int x=0,f=1,c=*++ptr;
        while(c<48)c=='-'&&(f=-1),c=*++ptr;
        while(c>47)x=x*10+c-48,c=*++ptr;
        return x*f;
    }
    int gcd(int a,int b){
        for(int c;b;c=a,a=b,b=c%b);
        return a;
    }
    int dis(int x,int y){
        return x*x+y*y;
    }
    int n,m,x[N],y[N],e[N],ans[N];
    bool re[N];
    struct tri{
        int a,b,c,d;
        tri(int w){
            int x1=x[w]-x[w-1],y1=y[w]-y[w-1],x2=x[w]-x[w+1],y2=y[w]-y[w+1];
            a=dis(x1,y1);
            b=dis(x2,y2);
            c=dis(x1-x2,y1-y2);
            int g=gcd(a,gcd(b,c));
            if(g>1)a/=g,b/=g,c/=g;
            d=x1*y2-x2*y1;
            d=d<0?-1:d>0;
        }
        bool operator<(tri w)const{
            return a!=w.a?a<w.a:b!=w.b?b<w.b:c!=w.c?c<w.c:d<w.d;
        }
    };
    std::map<tri,int>nx[N];
    int p=1,fa[N],deg[N],t[N],q[N],ql=0,qr=0;
    int main(){
        buf[fread(buf,1,sizeof(buf),stdin)]=0;
        n=_();m=_();
        for(int i=0;i<m;++i){
            int c=_();
            for(int j=0;j<c;++j){
                x[j]=_();y[j]=_();
            }
            if(c<3)ans[i]=n+1-c,re[i]=1;
            else{
                int w=1;
                for(int j=2;j<c;++j){
                    tri t(j-1);
                    if(t.d)re[i]=1;
                    if(nx[w].find(t)==nx[w].end())nx[w][t]=++p;
                    w=nx[w][t];
                }
                e[i]=w;
            }
        }
        ql=qr=0;q[++qr]=1;
        while(ql!=qr){
            int w=q[++ql];
            for(std::map<tri,int>::iterator it=nx[w].begin();it!=nx[w].end();++it){
                int u=it->second,v=fa[w];
                q[++qr]=u;
                while(v&&nx[v].find(it->first)==nx[v].end())v=fa[v];
                fa[u]=v?nx[v][it->first]:1;
            }
        }
        for(int i=0;i<n;++i){
            x[i]=_();y[i]=_();
        }
        int w=1;
        for(int i=2;i<n;++i){
            tri t(i-1);
            while(w&&nx[w].find(t)==nx[w].end())w=fa[w];
            w=w?nx[w][t]:1;
            ++::t[w];
        }
        for(int i=0;i<n;++i)y[i]=-y[i];
        w=1;
        for(int i=2;i<n;++i){
            tri t(i-1);
            while(w&&nx[w].find(t)==nx[w].end())w=fa[w];
            w=w?nx[w][t]:1;
            ++::t[w];
        }
        ql=qr=0;
        for(int i=1;i<=p;++i)++deg[fa[i]];
        for(int i=1;i<=p;++i)if(!deg[i])q[++qr]=i;
        deg[0]=0x3f3f3f3f;
        while(ql!=qr){
            int w=q[++ql],f=fa[w];
            t[f]+=t[w];
            if(!--deg[f])q[++qr]=f;
        }
        for(int i=0;i<m;++i)if(e[i])ans[i]=t[e[i]];
        for(int i=0;i<m;++i)printf("%d\n",re[i]?ans[i]:ans[i]>>1);
        return 0;
    }
    
    • 1

    信息

    ID
    3766
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者