題目描述

給出平面上的兩個點集，如果其中一個點集可以通過擴大、縮小、旋轉、翻轉、移動等操作變換到另一個點集，那么我們就稱這兩個點集相似。舉個例子：點集{(0,0),(2,0),(2,1)}$/{(0,0), (2,0), (2,1)/}$和點集{(6,1),(6,5),(4,5)}$/{(6,1), (6,5), (4,5)/}$相似，但是不和點集{(4,0),(6,0),(5,?1)}$/{(4,0),(6,0), (5,-1)/}$相似。給出點集求他們是否相似。

輸入

第一行一個數k(1≤k≤25000)$k (1/le k/le 25000)$表示第一個點集的點的個數。 接下來k$k$行每行描述一個點：xiyi(?20000≤xi,yi≤20000)$x_i/; y_i (-20000/le x_i, y_i/le 20000)$。不存在兩點坐標相同。 接下來一個數：n(1≤n≤20)$n (1/le n/le 20)$表示有多少個點集要檢測。接下來n$n$個點集的描述，和上面相同。

輸出

對于每個要測試的點集，如果它和第一個點集相似，那么打印TAK(YES in Polish)，否則打印NIE(NO in Polish)。

樣例輸入

30 02 02 1234 16 54 534 06 05 -1
樣例輸出
TAKNIE
一開始看到這題，以為只要隨便轉一轉，放縮一下，翻轉一下，找一個基準點排個序，再暴力判一下就好了。 然后發現自己真的是naive，因為轉這個東西不一定轉多少度的……
對于一個點集，應該取它的重心（(xˉ,yˉ)$(/bar x,/bar y)$）為基準點。 首先，如果兩個點集大小不同，那么一定不相似。 然后將點集按極角為第一鍵值，極距其次排序，再將其轉化為相鄰兩點的極角差和極距比的序列。如果兩個點集相似，那么這兩個序列是循環同構的。極距比直接縮放了，極角差避免了處理旋轉角…… 還差一個鏡像，則只要將x$x$或y$y$坐標取相反數后再次計算即可。 注意刨掉極距為0$0$的點…… 時間復雜度O(nlog2n)$O(n/log_2n)$。 %%%Claris
代碼
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;typedef long double ld;const ld eps=1e-10, pi=acos(-1);// 定義點/向量/存儲兩個double的結構體struct dot{    ld x, y;    dot(){}    dot(ld X, ld Y):x(X), y(Y){}    bool Operator<(const dot &a)const{        return fabs(x-a.x)<=eps?y<a.y:x<a.x;    }    bool operator==(const dot &a)const{        return fabs(x-a.x)<=eps&&fabs(y-a.y)<=eps;    }    bool operator!=(const dot &a)const{        return !(*this==a);    }    friend dot operator+(const dot &a, const dot &b){        return dot(a.x+b.x, a.y+b.y);    }    friend dot operator/(const dot &a, const double &b){        return dot(a.x/b, a.y/b);    }};// 定義點集struct ss{    int k;    // arr:點 mp:重心 ang:極角極距 cir:相鄰點求的序列    dot arr[25010], mp, ang[25010], cir[25010];    // 處理點集    void PRo(){        mp=dot(0, 0);        for(int i=0;i<k;i++)            mp=mp+arr[i];        mp=mp/k;        // 特判和重心重合的點        for(int i=0;i<k;i++)            if(arr[i]==mp){                swap(arr[i], arr[k-1]);                k--; i--;            }        // 計算ang和cir        for(int i=0;i<k;i++)            ang[i].x=atan2(arr[i].y-mp.y, arr[i].x-mp.x),            ang[i].y=hypot(arr[i].x-mp.x, arr[i].y-mp.y);        sort(ang, ang+k);        for(int i=0;i<k-1;i++)            cir[i].x=ang[i].x-ang[i+1].x,            cir[i].y=ang[i].y/ang[i+1].y;        cir[k-1].x=ang[k-1].x-ang[0].x-pi*2,        cir[k-1].y=ang[k-1].y/ang[0].y;    }}A, B;int n, k;inline int rd(){    int a=0, f=1; char c=getchar();    while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}    while(isdigit(c)) (a*=10)+=c-'0', c=getchar();    return a*f;}// 最小表示法int mini(const ss &a){    int i=0, j=1;    while(i<k&&j<k){        int l=0;        while(l<k&&a.cir[(i+l)%k]==a.cir[(j+l)%k]) l++;        if(l==k) return i;        if(a.cir[(i+l)%k]<a.cir[(j+l)%k]) j=j+l+1;        else i=i+l+1;        if(i==j) j++;    }    return min(i, j);}// 判斷點集相等bool cmp(const ss &a, const ss &b, int sta, int stb){    for(int i=0;i<k;i++)        if(a.cir[(sta+i)%k]!=b.cir[(stb+i)%k])            return false;    return true;}int main(){    A.k=rd();    for(int i=0;i<A.k;i++)        A.arr[i].x=rd(), A.arr[i].y=rd();    A.pro(); k=A.k;    int sta=mini(A);    n=rd();    while(n--){        B.k=rd();        for(int i=0;i<B.k;i++)            B.arr[i].x=rd(), B.arr[i].y=rd();        B.pro();        // 點集大小不同        if(A.k!=B.k){            puts("NIE");            continue;        }        int stb=mini(B);        if(cmp(A, B, sta, stb)){puts("TAK"); continue;}        // 翻轉        for(int i=0;i<k;i++) B.arr[i].x*=-1;        B.pro(); stb=mini(B);        if(cmp(A, B, sta, stb)) puts("TAK");        else puts("NIE");    }    return 0;}
其實如果知道了重心和處理序列的話這題還是比較容易的。 （為啥用long double？） 因為不知道為啥被卡精度了！eps取1e8$1e8$時候卡了4號9號點，取1e10$1e10$時候被卡了10號點……感覺并沒有很多乘除啊……改了改貌似跟Claris差不多依然被卡…… 怒取long double……