判断两个凸包是否同构

首先将两个点集都求凸包，然后根据边角边建立两个串。接下来就是double类型的最小表示法。。魔改一下就好了。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
const double EPS = 1e-6;
const int INF = 0x7fffffff;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x;
        double yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }
    void input()
    {
        scanf("%lf%lf", &x, &y);
    }

    bool operator <(Point &rhs)
    {
        if(fabs(y - rhs.y) <= EPS) return x < rhs.x;
        return y < rhs.y;
    }
    double x, y;
    double v, l;
    int id;
};
Point operator -(Point lhs, Point rhs){return Point(rhs.x - lhs.x, rhs.y - lhs.y);}
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
double operator *(Point lhs, Point rhs){return lhs.x * rhs.x + lhs.y * rhs.y;}

Point src1, src2, src;
int n, m;

bool cmp(Point &a, Point &b)
{
    double temp = (a - src) ^ (b - src);
    if(fabs(temp) <= EPS) return a.getDis(src) < b.getDis(src);
    return temp > 0;
}

int stack[MAXN];
void getConvex(vector<Point> &a, vector<Point> &out)
{
    out.clear();
    sort(a.begin(), a.end(), cmp);

    stack[0] = 0;
    stack[1] = 1;
    int top = 1;
    for(int i = 2; i < (int)a.size(); ++i)
    {
        while(top >= 1 && ((a[i] - a[stack[top - 1]]) ^ (a[stack[top]] - a[stack[top - 1]])) >= 0)
        {
            --top;
        }
        stack[++top] = i;
    }
    for(int i = 0; i <= top; ++i) out.push_back(a[stack[i]]);
}

vector<Point> c1, c2, a1, a2;

vector<double> d1, d2;
vector<double> r1, r2;

void smallrep(vector<double> &d, vector<double> &out)
{
    int i, j, k, l;
    int n = (int)d.size();
    for(i = 0; i < n; ++i)
    {
        d.push_back(d[i]);
    }
    for(i = 0, j = 1; j < n;)
    {
        for(k = 0; k < n && fabs(d[i + k] - d[j + k]) <= EPS; ++k);
        if(k >= n) break;
        if(d[i + k] < d[j + k]) j += k + 1;
        else
        {
            l = i + l;
            i = j;
            j = max(l, j) + 1;
        }
    }
    out.clear();
    for(int t = i; t < i + n; ++t)
    {
        out.push_back(d[t]);
    }
}

void smallest(vector<double> &d, vector<double> &out)
{
    int n = (int)d.size();
    for(int i = 0; i < n; ++i)
    {
        d.push_back(d[i]);
    }
    int i = 0, p = 1;
    while(i < n && p < n)
    {
        int k = 0;
        while(fabs(d[i + k] - d[p + k]) <= EPS) ++k;
        if(k >= n) break;

            if(d[i + k] > d[p + k]) i = max(i + k + 1, p + 1);
            else p = max(p + k + 1, i + 1);
    }
    i = min(i, p);
    for(int t = i; t < i + n; ++t)
    {
        out.push_back(d[t]);
    }
}

bool small()
{
    int n = c1.size(), m = c2.size();
    if(n != m) return false;
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        int pre = (i - 1 + n) % n;
        Point preVec = c1[pre] - c1[i];
        Point nxtVec = c1[nxt] - c1[i];
        d1.push_back(c1[i].getDis(c1[nxt]));
        d1.push_back(fabs(preVec * nxtVec));
    }
    for(int i = 0; i < m; ++i)
    {
        int nxt = (i + 1) % m;
        int pre = (i - 1 + n) % n;
        Point preVec = c2[pre] - c2[i];
        Point nxtVec = c2[nxt] - c2[i];
        d2.push_back(c2[i].getDis(c2[nxt]));
        d2.push_back(fabs(preVec * nxtVec));
    }
    smallest(d1, r1);
    smallest(d2, r2);
    n = r1.size();
    for(int i = 0; i < n; ++i)
    {
        if(fabs(r1[i] - r2[i]) >= EPS) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    Point temp;
    for(int i = 1; i <= n; ++i)
    {
        temp.input();
        a1.push_back(temp);
        if(i == 1) src1 = temp;
        else
        {
            if(temp < src1) src1 = temp;
        }
    }
    for(int i = 1; i <= m; ++i)
    {
        temp.input();
        a2.push_back(temp);
        if(i == 1) src2 = temp;
        else
        {
            if(temp < src2) src2 = temp;
        }
    }
    src = src1;
    getConvex(a1, c1);
    src = src2;
    getConvex(a2, c2);
    if(small()) puts("YES");
    else puts("NO");
}