题解：P8142 [ICPC 2020 WF] Which Planet is This?!

· · 题解

最小表示法好题。

题目传送门。

前置知识：最小表示法。

已经过 @ctzm 同意，感谢 ctzm 的题解 对我的帮助。

\texttt {solution}

最开始看到这题，第一反应是把所有坐标按照 x 大小排序，然后比较所有的 y 坐标是否对应相等。

但是这个方法有问题。原因是，旋转后的 y 坐标需要对 360 取模，有些很大的坐标取模后就变小了，该方法不可行（读者也可以想想为什么）。

然后我们就发现一个很有趣的性质，即把 y 坐标从小到大排序，做差分，然后你发现无论怎么旋转这颗星球，差分都是不变的。

欸！这个时候是不是就很好做了！这样就变成了两颗星球是否有一种排列坐标的方式，使得 x 坐标一一对应的同时，y 坐标的差分也是对应的。那么就是说这两组坐标循环同构，那么就用最小表示法排列然后比较即可。

\texttt{Code}

有一点要注意的是输入，不妨将所有坐标全部乘上 10000 转化为整数。

复杂度 \mathcal O\left(n\log n \right)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n;
const int N = 8e5 + 10, mod = 3600000;
struct pos {
    int x, y;
    bool operator < (const pos &W) const {
        if(y != W.y) return y < W.y;
        return x < W.x;
    }
    bool operator > (const pos &W) const {
        if(y != W.y) return y > W.y;
        return x > W.x;
    }
    bool operator != (const pos &W) const {
        if(x != W.x || y != W.y) return 1;
        return 0;
    }
    void print() {
        cout << x << ' ' << y << endl;
    }
} a[N], b[N];
int posa, posb;
void getxy(pos &now) {
    string s;
    cin >> s;
    int nx = 0, ny = 0;
    int f = 1, dot = 0, dotnum = 4;
    for (int i = 0; i < s.size(); i ++) {
        if(s[i] == '-') f = -1;
        else if(s[i] == '.') dot = 1;
        else if(isdigit(s[i])) {
            nx *= 10;
            nx += s[i] - '0';
            dotnum -= dot;
        }
    }
    nx *= f;
    nx = nx * pow(10, dotnum);
    cin >> s;
    f = 1;
    dotnum = 4, dot = 0;
    for (int i = 0; i < s.size(); i ++) {
        if(s[i] == '-') f = -1;
        else if(s[i] == '.') dot = 1;
        else if(isdigit(s[i])) {
            ny *= 10;
            ny += s[i] - '0';
            dotnum -= dot;
        }
    }
    ny *= f;
    ny = ny * pow(10, dotnum);
    now = {nx, ny};
}
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        getxy(a[i]);
    }
    for (int i = 1; i <= n; i ++) {
        getxy(b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    a[n + 1].y = a[1].y + 3600000;
    b[n + 1].y = b[1].y + 3600000;
    for (int i = 1; i <= n; i ++) {
        a[i].y = a[i + 1].y - a[i].y;
        b[i].y = b[i + 1].y - b[i].y;
    }
    for (int i = 1; i <= n; i ++) {
        a[i + n] = a[i];
        b[i + n] = b[i];
    }
    int i1 = 1, j1 = 2, k1 = 0;
    while (i1 <= n && j1 <= n) {
        if(i1 == j1) j1 ++;
        while (k1 < n) {
            if(a[i1 + k1] != a[j1 + k1]) break;
            k1 ++;
        }
        if(a[i1 + k1] > a[j1 + k1]) i1 += k1 + 1;
        else j1 += k1 + 1;
        k1 = 0;
    }
    posa = min(i1, j1);
    i1 = 1, j1 = 2, k1 = 0;
    while (i1 <= n && j1 <= n) {
        if(i1 == j1) j1 ++;
        while (k1 < n) {
            if(b[i1 + k1] != b[j1 + k1]) break;
            k1 ++;
        }
        if(b[i1 + k1] > b[j1 + k1]) i1 += k1 + 1;
        else j1 += k1 + 1;
        k1 = 0;
    }
    posb = min(i1, j1);
    for (int i = 1; i <= n; i ++) {
        if(a[i + posa] != b[i + posb]) return cout << "Different", 0;
    }
    cout << "Same";
    return 0;
}