首页 > 代码库 > 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