[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;
}