Codeforces #502 E. The Supersonic Rocket

まぁE,Fがまともに解けなかったのでUnratedで助かったかも。
http://codeforces.com/contest/1017/problem/E

問題

２次元座標において２つの頂点群が与えられる。
各頂点群は、頂点群内の全頂点を同時に並行移動または原点を中心とした回転が可能である。

上記移動を適切に行った場合、両頂点群において頂点間を線形補間する位置に頂点を増やすということを繰り返し行った場合、両図形の形状が一致する状態にできるか判定せよ。

解法

問題文後半がわかりにくいが、これは結局凸包のことを言っているだけである。
よってまず元の頂点群においてそれぞれ凸包を求め、その合同判定を行えばよい。
合同判定はいくつか方法があるようだ。

• 辺の長さの配列を作り、Z-Algorithmで片方をRotateしてもう片方に一致するか判定
• 重心を原点に持ってくるように平行移動する。
  • その後、頂点からの距離と隣接点に対する相対的な偏角の配列を作り、Z-Algorithmで判定
  • 両頂点群に対し、原点からの距離が一致するペアを１つ求め、その回転角から、頂点群全体をその回転角分を戻すと一致するか判定する。

後者は一見O(|V|^2)かかりそうだが、元の頂点群に同じ位置の頂点がないというのと、各頂点が格子点にあるという条件から、「原点からの距離が一致するペア」がそんなにないのでO(|V|)で済む。
以下のコードは最後の方法を取っている。

int N,M;
vector<pair<ll,ll>> A,B;
vector<pair<long double,long double>> C,D;

const ll EPS=0;
template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}

pair<long double,long double> center(vector<pair<long double,long double>> V) {
	if(V.size()==1) return V[0];
	if(V.size()==2) return {(V[0].first+V[1].first)/2,(V[0].second+V[1].second)/2};
	
	long double dx=0,dy=0,A=0;
	int i;
	for(i=1;i<V.size()-1;i++) {
		long double cx=(V[0].first+V[i].first+V[i+1].first)/3;
		long double cy=(V[0].second+V[i].second+V[i+1].second)/3;
		
		long double cr=abs((V[i].first-V[0].first)*(V[i+1].second-V[0].second)-(V[i+1].first-V[0].first)*(V[i].second-V[0].second));
		A+=cr;
		dx+=cx*cr;
		dy+=cy*cr;
	}
	assert(A);
	return {dx/A,dy/A};
}

vector<pair<long double,long double>> hoge(vector<pair<ll,ll>> A) {
	vector<pair<long double,long double>> C;
	auto v=convex_hull(A);
	long double dx=0,dy=0;
	FORR(c,v) {
		C.push_back({A[c].first,A[c].second});
	}
	auto ce=center(C);
	FORR(c,C) c.first-=ce.first,c.second-=ce.second;
	return C;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		A.push_back({x,y});
	}
	FOR(i,M) {
		cin>>x>>y;
		B.push_back({x,y});
	}
	
	C=hoge(A);
	D=hoge(B);
	N=C.size();
	M=D.size();
	if(N!=M) return _P("NO\n");
	FOR(i,N) if(abs(hypot(C[i].first,C[i].second)-hypot(D[0].first,D[0].second))<1e-2) {
		long double deg=atan2(D[0].second,D[0].first)-atan2(C[i].second,C[i].first);
		
		FOR(j,N) {
			long double dx=C[j].first*cos(deg)-C[j].second*sin(deg);
			long double dy=C[j].first*sin(deg)+C[j].second*cos(deg);
			if(abs(dx-D[(j+N-i)%N].first)+abs(dy-D[(j+N-i)%N].second)>1e-2) break;
		}
		if(j==N) return _P("YES\n");
		
		
	}
	
	_P("NO\n");
	
	
	
}

まとめ

実装はともかく、問題文が無駄に難しくない？
凸包と言い切っちゃえばいいのに。