专栏文章

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

NN1tr0us_Acid
P8142题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2wjjk
此快照首次捕获于
2025/12/02 12:29
3 个月前
此快照最后确认于
2025/12/02 12:29
3 个月前
查看原文
最小表示法好题。
题目传送门。
前置知识：最小表示法。
已经过 ctzm同意，感谢 ctzm 的题解 对我的帮助。

solution\texttt {solution}

最开始看到这题，第一反应是把所有坐标按照 xx 大小排序，然后比较所有的 yy 坐标是否对应相等。
但是这个方法有问题。原因是，旋转后的 yy 坐标需要对 360360 取模，有些很大的坐标取模后就变小了，该方法不可行（读者也可以想想为什么）。
然后我们就发现一个很有趣的性质，即把 yy 坐标从小到大排序，做差分，然后你发现无论怎么旋转这颗星球，差分都是不变的。
欸！这个时候是不是就很好做了！这样就变成了两颗星球是否有一种排列坐标的方式，使得 xx 坐标一一对应的同时，yy 坐标的差分也是对应的。那么就是说这两组坐标循环同构，那么就用最小表示法排列然后比较即可。

Code\texttt{Code}

有一点要注意的是输入，不妨将所有坐标全部乘上 1000010000 转化为整数。
复杂度 O(nlog⁡n)\mathcal O\left(n\log n \right)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...