kmjp's blog

競技プログラミング参加記です

Codeforces #618 Div1 B. Aerodynamic

いまいち何がしたいかわからなかった問題。
https://codeforces.com/contest/1299/problem/B

問題

2次元座標において、凸である多角形Pを考える。
Pを回転させることなく(0,0)を含むように平行移動したときにPに含まれる範囲を和の領域をTとする。
PとTは相似かどうか判定せよ。

解法

Pの相対する辺が平行かつ同じ長さならよく、結局Pが点対称ならよい。
このときTはPと相似で2倍に拡大した形状になる。
そこで、Pの頂点数が偶数か確認し、相対する点との中点が全点で一致するか確認しよう。

int N;
ll X[101010],Y[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
	}
	
	if(N%2) return _P("NO\n");
	
	set<pair<ll,ll>> S;
	FOR(i,N/2) {
		S.insert({X[i]+X[i+N/2],Y[i]+Y[i+N/2]});
	}
	if(S.size()==1) {
		cout<<"YES"<<endl;
	}
	else {
		cout<<"NO"<<endl;
	}
	
}

まとめ

実装はとても軽い。