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

  

上一篇:【commons】Bean工具类——commons-beanutils之BeanUtils


下一篇:fragment嵌套,viewpager嵌套 不能正确显示