自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:48:48，当前版本为作者最后更新于2017-09-11 01:26:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【POI补全计划#2 POI2005 PUN】

先说题目大意：

给定两个点集，判断是否相似，相似输出TAK，不相似输出NIE

相似的定义是可以经过四种操作后重合（平移，旋转，翻转，防缩）

多组数据（具体输入方式见题目）

----------------题解分割线-------------------

这题本来是个很水的题，但是卡我精度卡了好久。。可能是我太菜了。。

简单来说就是找到点集的重心（所有点加起来除以点的个数），

然后将所有点标准化至【最长的线段长度为1，重心在原点上】

这样就解决了平移和防缩的问题

接下来对极角排序后差分一下（第二关键字为长度）

最后由于圆上的整点个数比较少，只需要暴力判断其中一个点集是否是另一个旋转/翻转后的结果就行了，不需要KMP

注意要特判有可能有点和重心重合

注意任何可能会被卡精度的地方

福利：原题地址

贴代码时间（不要吐槽我不小心面向对象了QWQ）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10,PI=3.1415926535897932384626;
const int MAXN=25050;
struct point
{
    double x,y;
    inline point(){}
    inline point(double xx,double yy){x=xx,y=yy;}
    inline point(const point &p){x=p.x,y=p.y;}
    inline point operator=(const point &p){x=p.x,y=p.y;return *this;}
    inline point operator+(const point &p)const{return point(x+p.x,y+p.y);}
    inline point operator+=(const point &p){return *this=*this+p;}
    inline point operator-(const point &p)const{return point(x-p.x,y-p.y);}
    inline point operator-=(const point &p){return *this=*this-p;}
    inline double operator*(const point &p)const{return x*p.x+y*p.y;}
    inline point operator/(const double &n)const{return point(x/n,y/n);}
    inline point operator/=(const double &n){return *this=*this/n;}
    inline bool operator==(const point &p)const{return abs(x-p.x)<eps&&abs(y-p.y)<eps;}
}set1[MAXN],set2[MAXN];
struct atom
{
    double len,deg;
    inline bool operator==(const atom &a)const
    {
        return abs(len-a.len)<eps&&abs(deg-a.deg)<eps;
    }
    inline bool operator!=(const atom &a)const
    {
        return !(*this==a);
    }
    inline bool operator<(const atom &a)const
    {
        return abs(deg-a.deg)<eps?len<a.len:deg<a.deg;
    }
}revarr1[MAXN],arr1[MAXN],arr2[MAXN];
inline bool cmp(const atom &a,const atom &b)
{
    return a.len<b.len;
}
inline bool cmp2(const atom &a,const atom &b)
{
    return abs(a.deg-b.deg)<eps?a.len<b.len:a.deg>b.deg;
}
inline double sqr(const double &x){return x*x;}
inline bool match(const atom arr1[],const atom arr2[],int len)
{
    static int tt=0;
    ++tt;
    for(int delta=0;delta<len;delta++)
    {
        bool flag=true;
        for(int i=1;i<=len;i++)
        {
            if(arr1[i]!=arr2[(i+delta-1)%len+1])
            {
                flag=false;
                break;
            }
        }
        if(flag)return true;
    }
    return false;
}
int main()
{
    int n,t,n2;
    bool havecenter=false,havecenter2;
    scanf("%d",&n);
    point c1(0,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&set1[i].x,&set1[i].y);
        c1+=set1[i];
    }
    c1/=n;
    for(int i=1;i<=n;i++)
    {
        if(!havecenter)set1[i]-=c1;
        else set1[i]=set1[i+1]-c1;
        if(set1[i]==point(0,0))
        {
            havecenter=true;
            n--;i--;
            continue;
        }
        arr1[i].len=sqrt(sqr(set1[i].x)+sqr(set1[i].y));
        arr1[i].deg=acos(set1[i].x/arr1[i].len);
        if(set1[i].y<0)arr1[i].deg=2*PI-arr1[i].deg;
    }
    sort(arr1+1,arr1+n+1,cmp);
    double maxlen=arr1[n].len;
    for(int i=1;i<=n;i++)
    {
        arr1[i].len/=maxlen;
        revarr1[i]=arr1[i];
    }
    sort(arr1+1,arr1+n+1);
    sort(revarr1+1,revarr1+n+1,cmp2);
    double maxdeg=arr1[n].deg;
    for(int i=n;i>=2;i--)
    {
        revarr1[n-i+2].deg=(arr1[i].deg-=arr1[i-1].deg);
    }
    revarr1[1].deg=arr1[1].deg+=2*PI-maxdeg;
    scanf("%d",&t);
    while(t--)
    {
        havecenter2=false;
        scanf("%d",&n2);
        for(int i=1;i<=n2;i++)
        {
            scanf("%lf%lf",&set2[i].x,&set2[i].y);
        }
        point c2(0,0);
        for(int i=1;i<=n2;i++)
        {
            c2+=set2[i];
        }
        c2/=n2;
        for(int i=1;i<=n2;i++)
        {
            if(!havecenter2)set2[i]-=c2;
            else set2[i]=set2[i+1]-c2;
            if(set2[i]==point(0,0))
            {
                havecenter2=true;
                n2--;i--;
                continue;
            }
            arr2[i].len=sqrt(sqr(set2[i].x)+sqr(set2[i].y));
            arr2[i].deg=acos(set2[i].x/arr2[i].len);
            if(set2[i].y<0)arr2[i].deg=2*PI-arr2[i].deg;
        }
        if(n2!=n)
        {
            printf("NIE\n");
            continue;
        }
        else if(n==0)
        {
            printf("TAK\n");
            continue;
        }
        sort(arr2+1,arr2+n2+1,cmp);
        double maxlen=arr2[n2].len;
        for(int i=1;i<=n2;i++)
        {
            arr2[i].len/=maxlen;
        }
        sort(arr2+1,arr2+n2+1);
        double maxdeg=arr2[n2].deg;
        for(int i=n2;i>=2;i--)
        {
            arr2[i].deg-=arr2[i-1].deg;
        }
        arr2[1].deg+=2*PI-maxdeg;
        bool f1=match(arr1,arr2,n),f2=match(revarr1,arr2,n);
        if(havecenter==havecenter2&&(f1||f2))printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}