Codeforces #271 Div2 C. Captain Marmot

CF271に参加。
だいぶ苦戦したけど、時間ぎりぎりで全完。なんとか全部正答。
時間かかりすぎて、順位はそこまででもない。
http://codeforces.com/contest/474/problem/C

問題

２次元座標上で、４つの点の位置(X[i],Y[i])とそれぞれのホームポジション(A[i],B[i])が与えられる。
各頂点は、ホームポジションを中心に90度反時計回りに移動できる。
それぞれの頂点を何度か移動させ、４頂点が面積が正の正方形を成す配置に出来るか。
また、その際必要な頂点の移動回数を答えよ。

解法

各頂点の移動回数は高々３回なので、各頂点を０～３回移動を総当たりすればよい。
あとは４頂点の正方形判定だが、自分は２頂点a,bで１辺を構築すると、aを中心にa→bのベクトルを左90度回転するのと、bを中心にb→aのベクトルを右90度回転して残り２点の位置を計算して判定した。

int N;
int X[4],Y[4],A[4],B[4];

pair<int,int> rot(int x,int y,int a,int b,int num) {
	while(num--) {
		int ox=x,oy=y;
		x=a+(b-oy);
		y=b-(a-ox);
	}
	return make_pair(x,y);
}

bool sq(pair<int,int> P1,pair<int,int> P2,pair<int,int> P3,pair<int,int> P4) {
	pair<int,int> p;
	if(P1==P2) return false;
	p.first=P2.first+(P1.second-P2.second);
	p.second=P2.second-(P1.first-P2.first);
	if(p!=P3) return false;
	p.first=P1.first+(P1.second-P2.second);
	p.second=P1.second-(P1.first-P2.first);
	return p==P4;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,4) cin>>X[j]>>Y[j]>>A[j]>>B[j];
		int ma=100;
		FOR(j,256) {
			pair<int,int> P[4];
			FOR(k,4) P[k]=rot(X[k],Y[k],A[k],B[k],(j>>(2*k))%4);
			x=j%4+j/4%4+j/16%4+j/64%4;
			if(sq(P[0],P[1],P[2],P[3])) ma=min(ma,x);
			if(sq(P[0],P[1],P[3],P[2])) ma=min(ma,x);
			if(sq(P[0],P[2],P[1],P[3])) ma=min(ma,x);
			if(sq(P[0],P[2],P[3],P[1])) ma=min(ma,x);
			if(sq(P[0],P[3],P[1],P[2])) ma=min(ma,x);
			if(sq(P[0],P[3],P[2],P[1])) ma=min(ma,x);
		}
		if(ma==100) ma=-1;
		cout << ma << endl;
	}
	
}

まとめ

正方形判定、よくありそうだけど面倒だな。
90度回転の計算式、毎回符号が混乱する。