bzoj1039: [ZJOI2008]无序运动Movement

#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;
}