[Codeforces] 1017E. The Supersonic Rocket

題目連結:https://codeforces.com/problemset/problem/1017/E

比賽unrated了,不知道好險還是好慘,前面做題真的做超慢,然後到現在還是不知道為什麼C那樣做就好了。
不過這題其實滿有趣的。
可以發現這題其實要問的就是兩個東東他們的凸包是否相同(允許旋轉及位移,但不能鏡射),原因就是會發現結束的時候,一個engine構成的power field一定會變成一個凸多邊形,然後現在考慮若是拆掉凸多邊形上任意一個頂點,那他必定會縮進去(沒有兩個點在相同的位置),所以我們一定要用另外一個engine來補,才可以讓他不會縮進去,也因此其實就是每個頂點都要在一樣的位置。
那要怎麼做呢?當然,先求出凸包之後,拿到的凸包顯然會按(順/逆)(看實作)時鐘的方式排序點,所以我們其實就是要求,兩個凸包是否有某種旋轉操作(abc->bca->cab...)使他們相同。
我原先是用booth's algorithm幫兩個東東都求出最小字典序的旋轉,再來一個一個比較是否一樣,但也有其他作法。
字串相關的作法就是將其中一個凸包複製一次貼在自己後面(abc->abcabc),然後hash或kmp直接求是否另一個凸包出現在裡面。
不過其實暴力枚舉一個東東旋轉後的長相然後判斷相等就可以過了,因為其實整數點上的凸包大小最多只有$\sqrt{C}$,所以直接枚舉的複雜度也才$\sqrt{C} \times \sqrt{C} = C$。
但這題最難的點,我覺得其實要怎麼把凸包變成一個序列,且他可以拿來判斷旋轉位移後可以一樣,但鏡射不行,原本我的想法只有判斷所有邊的長度跟所有角的角度是否一樣,但是卻被Hack掉了,後來才發現我需要把角跟邊擺在一起才可以成立,不然鏡射的話他拿的邊順序及角順序也可以一樣,但實際卻長得不一樣。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) begin(x), end(x)
#define SZ(x) (static_cast<int>((x).size()))
using lld = int64_t;

struct PT{
	lld x, y;
	PT(): x(0), y(0){}
	PT(lld a, lld b): x(a), y(b){}
	PT operator-(const PT& a) const {return PT(x-a.x, y-a.y);}
};
lld dot(const PT& a, const PT& b) {
	return a.x*b.x + a.y*b.y;
}
lld cross(const PT& a, const PT& b) {
	return a.x * b.y - a.y * b.x;
}

class ConvexHull_2D{
private:
	vector<PT> dots;
public:
	inline void init(){dots.clear();}
	void insert(const PT& x){dots.PB(x);}
	void solve(){
		sort(ALL(dots), [](const PT& a, const PT& b){
		  return tie(a.x, a.y) < tie(b.x, b.y);
		});
		vector<PT> stk(SZ(dots)<<1);
		int top = 0;
		for(auto p: dots){
			while(top >= 2 and cross(p-stk[top-2], stk[top-1]-stk[top-2]) <= 0)
				top --;
			stk[top++] = p;
		}
		for(int i=SZ(dots)-2, t = top+1;i>=0;i--){
			while(top >= t and cross(dots[i]-stk[top-2], stk[top-1]-stk[top-2]) <= 0)
				top --;
			stk[top++] = dots[i];
		}
		stk.resize(top-1);
		swap(stk, dots);
	}
	vector<PT> get(){return dots;}
};
ConvexHull_2D cv;

inline bool check(const vector<lld>&,const vector<lld>&);

vector<lld> get_it(const vector<PT>& a) {
	vector<lld> ret;
	ret.PB(dot(a.back() - a[0], a.back() - a[0]));
	ret.PB(dot(a.back() - a[0], a[1] - a[0]));
	for(int i=1;i<SZ(a)-1;i++){
		ret.PB(dot(a[i-1] - a[i], a[i-1] - a[i]));
		ret.PB(dot(a[i-1] - a[i], a[i+1] - a[i]));
	}
	ret.PB(dot(a[SZ(a)-2] - a[SZ(a)-1], a[SZ(a)-2] - a[SZ(a)-1]));
	ret.PB(dot(a[SZ(a)-2] - a[SZ(a)-1], a[0] - a[SZ(a)-1]));
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	cv.init();
	for(int i=0;i<n;i++) {
		lld x, y; cin >> x >> y;
		cv.insert(PT(x, y));
	}
	cv.solve();
	vector<PT> one = cv.get();
	cv.init();
	for(int i=0;i<m;i++) {
		lld x, y; cin >> x >> y;
		cv.insert(PT(x, y));
	}
	cv.solve();
	vector<PT> two = cv.get();
	if(SZ(one) != SZ(two) or \
		!check(get_it(one), get_it(two)))
		cout << "NO" << '\n';
	else cout << "YES" << '\n';
	return 0;
}

inline bool check(const vector<lld>& a,const vector<lld>& b){
	for(int i=0;i<SZ(a);i++) {
		bool flag = true;
		for(int j=0;j<SZ(b);j++) {
			flag &= (a[(i+j)%SZ(a)] == b[j]);
			if(!flag) break;
		}
		if(flag) return true;
	}
	return false;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology