首页 > 代码库 > BZOJ1527 : [POI2005]Pun-point
BZOJ1527 : [POI2005]Pun-point
求出重心,然后把所有点关于重心极角排序,极角相同的按到重心距离从大到小排序。
按极角序依次扫描,得到相邻两个向量的夹角以及长度之比,看成字符串。
若两个字符串循环同构,则两个点集相似,KMP判断即可。
时间复杂度$O(n\log n)$。
#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=25010;const double eps=1e-10;int T,l,i,j,k,nxt[N];inline int sgn(double x){ if(x<-eps)return -1; if(x>eps)return 1; return 0;}struct P{ double x,y,o; P(){} P(double _x,double _y){x=_x,y=_y;} P operator+(const P&b){return P(x+b.x,y+b.y);} P operator-(const P&b){return P(x-b.x,y-b.y);} P operator/(double b){return P(x/b,y/b);} bool operator==(const P&b){return !sgn(x-b.x)&&!sgn(y-b.y);} bool operator!=(const P&b){return sgn(x-b.x)||sgn(y-b.y);} void cal(){o=atan2(y,x);} double operator*(const P&b){return x*b.x+y*b.y;} double len(){return sqrt(x*x+y*y);} double lensqr()const{return x*x+y*y;}}a[N],b[N],O;inline bool cmp(const P&a,const P&b){ if(!sgn(a.o-b.o))return a.lensqr()>b.lensqr(); return a.o<b.o;}struct Set{ int n,m;P f[N]; void init0(){ n=l; for(i=0;i<n;i++)a[i]=b[i]; } void init1(){ n=l; for(i=0;i<n;i++)a[i]=b[i],a[i].x*=-1; } void init(){ O=P(0,0); for(i=0;i<n;i++)O=O+a[i]; O=O/((double)n); for(i=j=m=0;i<n;i++)if(a[i]==O)m++;else a[j++]=a[i]; n=j; for(i=0;i<n;i++)a[i]=a[i]-O,a[i].cal(); if(!n)return; sort(a,a+n,cmp); a[n]=a[0]; for(i=0;i<n;i++)f[i]=P(a[i]*a[i+1]/a[i].len()/a[i+1].len(),a[i].len()/a[i+1].len()); for(nxt[0]=j=-1,i=1;i<n;nxt[i++]=j){ while(~j&&f[j+1]!=f[i])j=nxt[j]; if(f[j+1]==f[i])j++; } }}A,B;void init(){ scanf("%d",&l); for(i=0;i<l;i++)scanf("%lf%lf",&b[i].x,&b[i].y);}bool check(){ if(A.n!=B.n||A.m!=B.m)return 0; if(!A.n)return 1; for(j=-1,k=0;k<2;k++)for(i=0;i<A.n;i++){ while(~j&&B.f[j+1]!=A.f[i])j=nxt[j]; if(B.f[j+1]==A.f[i]){ j++; if(j==A.n-1)return 1; } } return 0;}int main(){ init(); A.init0(); A.init(); scanf("%d",&T); while(T--){ init(); B.init0(); B.init(); if(check()){puts("TAK");continue;} B.init1(); B.init(); puts(check()?"TAK":"NIE"); } return 0;}
BZOJ1527 : [POI2005]Pun-point
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。