BZOJ1527POI 2005 Point

BZOJ1527/POI 2005 Point

相似点集有一个性质,重心在点集中的位置是相同的,可以通过点集的重心判断现点集是否能还原成原点集.
如果两个点集的点数不同,肯定是不相似的.

1. 移动:直接根据重心的位置,确定现点集的移动方式,使得两个点集的重心重合.
2. 缩放:根据两个点集内的点到重心的最短距离确定缩放比例,注意如果最短距离是0要特判.
3. 旋转:根据每个点到重心的极角给两个点集内的点排序.
   每个点记录两个参数:①到重心的距离,②排完序后与下一个点的夹角大小.记为序列A.
   若两个点集是相似的,它们各自的A序列是循环同构的.那就可以通过最小表示法或者KMP算法判断是否是循环同构,从而确定两者是否相似.
4. 翻转:将现点集的横坐标全部取反再进行以上判断.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int M=25005;
const double eps=1e-8;
double add[5],pi,mn;
int n,m,flag=-1,tot,pre[M*2];
double tx[M],ty[M];
struct node{double a,b,d;bool operator<(const node &t)const{if(fabs(a-t.a)>eps)return a<t.a;return d<t.d;}bool operator==(const node &t)const{return fabs(b-t.b)<=eps&&fabs(d-t.d)<=eps;}bool operator>(const node &t)const{if(fabs(b-t.b)>eps)return b>t.b;return d>t.d;}
};
struct Point{double x,y;Point operator-(const Point t)const{Point a;a.x=x-t.x,a.y=y-t.y;return a;}Point operator+(const Point t)const{Point a;a.x=x+t.x,a.y=y+t.y;return a;}int Q(){if(y>=0){if(x>=0)return 1;return 2;}if(x>0)return 4;return 3;}
};
double dis(Point a,Point b){Point c=a-b;return sqrt(c.x*c.x+c.y*c.y);
}
struct Point_set{node s[M*2];//表示点集 Point p[M*2],cen;void set_cen(){cen.x=cen.y=0;for(int i=0;i<tot;i++)cen=cen+p[i];cen.x/=tot,cen.y/=tot;}double mndis(){double mi=2e9;for(int i=0;i<tot;i++){s[i].d=dis(p[i],cen);if(s[i].d>eps)mi=min(mi,s[i].d);else flag=i;}return mi;}void get_angle(){for(int i=0;i<m;i++){Point t=p[i]-cen;if(t.x==0){s[i].a=pi/2;}else s[i].a=atan(t.y/t.x);s[i].a+=add[t.Q()];s[i].d=sqrt(t.x*t.x+t.y*t.y);}sort(s,s+m);for(int i=0;i<m;i++){if(i<m-1)s[i].b=s[(i+1)%m].a-s[i].a;else s[i].b=2*pi-s[i].a+s[0].a;s[i+m]=s[i];}}
}A,B;
void Pre(){int i,j,k;tot=m;pi=atan(1)*4;add[1]=0;add[2]=add[3]=pi;add[4]=2*pi;A.set_cen();//找到重心 mn=A.mndis();if(~flag){swap(A.p[flag],A.p[m-1]);m--;}A.get_angle();pre[0]=-1;for(i=1,j=-1;i<m;i++){while(j>=0&&!(A.s[j+1]==A.s[i]))j=pre[j];if(A.s[j+1]==A.s[i])j++;pre[i]=j;}
}
bool match(node s1[],node s2[]){//长度都为m int i,j=-1,k=0,len=m*2;for(i=0;i<len;i++){while(j>=0&&!(s1[j+1]==s2[i]))j=pre[j];if(s1[j+1]==s2[i])j++;if(j==m-1)return true;}return false;
}
bool chk(){if(m<=1)return true;flag=-1;B.set_cen();double dis=B.mndis();double k=mn/dis;if(tot!=m&&flag==-1){return false;}if(tot==m&&flag!=-1){return false;}if(~flag)swap(B.p[flag],B.p[tot-1]);Point t=A.cen-B.cen;B.cen=B.cen+t;for(int i=0;i<m;i++){// x,y * mn/disB.p[i]=B.p[i]+t;B.p[i].x=B.cen.x+(B.p[i].x-B.cen.x)*k;B.p[i].y=B.cen.y+(B.p[i].y-B.cen.y)*k;}B.get_angle();//现在就剩匹配了if(match(A.s,B.s))return true;return false; 
}
void solve(){while(n--){int k;scanf("%d",&k);for(int i=0;i<k;i++)scanf("%lf %lf",&B.p[i].x,&B.p[i].y);if(k!=tot){puts("NIE");continue;}else {if(chk()){puts("TAK");continue;}for(int i=0;i<tot;i++)B.p[i].x*=(-1);if(chk())puts("TAK");else puts("NIE");}}
}
int main(){int i,k;scanf("%d",&m);tot=m;for(i=0;i<m;i++)scanf("%lf %lf",&A.p[i].x,&A.p[i].y);Pre();scanf("%d",&n);solve();return 0;
}