1 条题解
-
0
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
- 上传者