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

· · 题解

纯最小表示法做法，应该是尽可能做的最简洁的。

题意：给你两个地图，有 n 个点分别是坐标 x,y。两个地图本质相同，当且仅当题面有一种方式一一对应，并且对应点 x 相同，y 的差值是固定的 k，对于所有点都适用（y 在模 360 意义下）。判断两个地图是否本质相同。

首先，题目的坐标是小数，最多 4 位（但是甚至有数据可能没有小数点）。为了简化，我们想到读入浮点数，乘上 10^4 再转成整数，但事实是会有浮点误差。直接下结论：必须写快读（或之类的处理）。

直接展示我的处理代码，该函数读入一个浮点数，并返回它的 10^4 倍：

int get(){
    string s;
    cin>>s;
    int sgn=1,res=0,dot=0,cnt=4;
    for(char i:s){
        if(i=='-')sgn=-1;
        if(i=='.')dot=1;
        if('0'<=i&&i<='9'){
            if(dot)cnt--;
            res=res*10+(i-'0');
        }
    }
    res=sgn*res*pow(10,cnt);
    return res;
}

然后，由于合法的判定是存在合法差值 k，不影响它们的两两之间的大小关系和差值，我们先按照 y 排个序。为了排序唯一，y 相等就按照 x 排序。然后，我们只需要判断两组点对应位置 x 是否相等就好了。

以上只是一个初步思路，因为 y 是要模 360 的，因此原本一个大值可能加上偏移量就变小了，直接排序比较是错的，但也肯定可以将其旋转得到正确的原序列。所以，我们需要判断有没有一种旋转方式使得 x 匹配，这就是最小表示法的应用之一。还有一个问题，即使 x 匹配，y 的相对大小正确，但我们依然需要 y 的绝对大小作为参考，例如下面这组数据：

3
1 50
2 100
3 150
1 66
2 127
3 148

就能理解了吧。注意到全局加 k，其差分数组是不变的，我们重新把每个点的 y 设置成差分即可。注意这是一个类似环形的差分。

总结以下，合法的判定是：

随机凭做题直觉就感觉感觉到这个条件也是充分的。不理解的看代码吧：

#include<bits/stdc++.h>
using namespace std;
int n,del1,del2;
pair<int,int> p[400040],q[400040];
int get(){
    string s;
    cin>>s;
    int sgn=1,res=0,dot=0,cnt=4;
    for(char i:s){
        if(i=='-')sgn=-1;
        if(i=='.')dot=1;
        if('0'<=i&&i<='9'){
            if(dot)cnt--;
            res=res*10+(i-'0');
        }
    }
    res=sgn*res*pow(10,cnt);
    return res;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){int a=get(),b=get();p[i]={b,a};}
    for(int i=0;i<n;i++){int a=get(),b=get();q[i]={b,a};}
    sort(p,p+n);
    sort(q,q+n);
    p[n]={p[0].first+3600000,0};
    for(int i=0;i<n;i++){
        p[i].first=p[i+1].first-p[i].first;
    }
    q[n]={q[0].first+3600000,0};
    for(int i=0;i<n;i++){
        q[i].first=q[i+1].first-q[i].first;
    }   
    int i=0,j=1,k=0;
    while(i<n&&j<n&&k<n){
        if(p[(i+k)%n]==p[(j+k)%n])k++;
        else if(p[(i+k)%n]<p[(j+k)%n])j=j+k+1,k=0;
        else i=i+k+1,k=0;
        if(i==j)i++;
    }
    del1=min(i,j);

    i=0,j=1,k=0;
    while(i<n&&j<n&&k<n){
        if(q[(i+k)%n]==q[(j+k)%n])k++;
        else if(q[(i+k)%n]<q[(j+k)%n])j=j+k+1,k=0;
        else i=i+k+1,k=0;
        if(i==j)i++;
    }
    del2=min(i,j);

    for(int i=0;i<n;i++){
        if(p[(i+del1)%n]!=q[(i+del2)%n]){
            cout<<"Different";
            return 0; 
        }
    }
    cout<<"Same";

    return 0;
}