自动搬运

查看原文

来自洛谷，原作者为

	ctzm 目标 J AK S 300 / CF紫名（因为我已经蓝名了 ||百亿年不玩引诱的半个引诱人

搬运于2025-08-24 22:36:20，当前版本为作者最后更新于2025-07-08 16:49:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题意：给你两个地图，有 $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$ 设置成差分即可。注意这是一个类似环形的差分。

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

• 按 $y$ 排序后，存在一种循环同构方案使得它们 $x$ 一一对应，$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;
}