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;

}