【计算几何】【POI2005】PUN-Point BZOJ1527

题目描述

给出平面上的两个点集，如果其中一个点集可以通过扩大、缩小、旋转、翻转、移动等操作变换到另一个点集，那么我们就称这两个点集相似。举个例子：点集{(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……