Codeforces #265 Div1 B. Restore Cube

人によってアプローチが異なりそう。
http://codeforces.com/contest/464/problem/B

問題

8つの3次元上の格子点の座標が与えられる。
ただし、それぞれどの値がX,Y,Z座標に相当するかわからない。

この8つの点が辺の長さが正の立方体の8頂点を構成できるか答えよ。

解法

X,Y,Zの順番については総当たりで１頂点6通りずつ試せばよい。
(1つだけは固定でよいので、6^7通り)

あとは8つの頂点が立方体を構成するか丁寧に検証していく。
自分は以下のようにやった。

• まず重心を求めて8つの点がそこから等距離Lにあるかチェック。
• 1個頂点を決め打ちして、残りの7頂点における決め打ち点からの距離が以下の3通りに分かれるかチェック。
  • Lの2/√3倍の距離(=立方体の1辺)になる点が3個
  • Lの2√2/√3倍の距離になる点が3個
  • Lの2倍の距離になる点が1個
• Lの2/√3倍の距離になる3つの点は正三角形になる
• Lの2√2/√3倍の距離になる3つの点は正三角形になる
• Lの2/√3倍の距離の点とLの2√2/√3倍の距離の点は、それぞれ距離が1辺と等しくなる組がある。

距離は2乗距離で持っておくと整数だけで処理できて誤差によるミスの心配がなくなる。

int tab[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
int I[8];
int OX[8][3];
int X[8],Y[8],Z[8];

int okok() {
	ll TX=0,TY=0,TZ=0,LL[8],L2[8][8];
	ll XX[8],YY[8],ZZ[8];
	int i,j;
	
	FOR(i,8) {
		TX+=OX[i][tab[I[i]][0]]*6;
		TY+=OX[i][tab[I[i]][1]]*6;
		TZ+=OX[i][tab[I[i]][2]]*6;
	}
	TX/=8; TY/=8; TZ/=8;
	
	// same len?
	FOR(i,8) {
		XX[i]=OX[i][tab[I[i]][0]]*6-TX;
		YY[i]=OX[i][tab[I[i]][1]]*6-TY;
		ZZ[i]=OX[i][tab[I[i]][2]]*6-TZ;
		LL[i]=XX[i]*XX[i]+YY[i]*YY[i]+ZZ[i]*ZZ[i];
		if(LL[i]!=LL[0]) return 0;
	}
	if(LL[0]==0) return 0;
	
	FOR(i,8) FOR(j,8) {
		L2[i][j]=(XX[j]-XX[i])*(XX[j]-XX[i])+(YY[j]-YY[i])*(YY[j]-YY[i])+(ZZ[j]-ZZ[i])*(ZZ[j]-ZZ[i]);
	}
	
	// dist from V[0]
	vector<int> V1,V2,V3;
	for(i=1;i<8;i++) {
		if(L2[0][i]==LL[0]*4) V3.push_back(i);
		if(L2[0][i]*3==LL[0]*4) V1.push_back(i);
		if(L2[0][i]*3==LL[0]*8) V2.push_back(i);
	}
	if(V1.size()!=3 || V2.size()!=3 || V3.size()!=1) return 0;
	if(L2[V1[0]][V1[1]]!=L2[0][V1[0]]*2) return 0;
	if(L2[V1[1]][V1[2]]!=L2[0][V1[0]]*2) return 0;
	if(L2[V1[0]][V1[2]]!=L2[0][V1[0]]*2) return 0;
	if(L2[V2[0]][V2[1]]!=L2[0][V1[0]]*2) return 0;
	if(L2[V2[1]][V2[2]]!=L2[0][V1[0]]*2) return 0;
	if(L2[V2[0]][V2[2]]!=L2[0][V1[0]]*2) return 0;
	
	FOR(i,3) {
		int ok=0;
		if(L2[V1[i]][V2[0]]*3!=LL[0]*4) ok++;
		if(L2[V1[i]][V2[1]]*3!=LL[0]*4) ok++;
		if(L2[V1[i]][V2[2]]*3!=LL[0]*4) ok++;
		if(ok!=1) return 0;
	}
	
	_P("YES\n");
	FOR(i,8) _P("%d %d %d\n",OX[i][tab[I[i]][0]],OX[i][tab[I[i]][1]],OX[i][tab[I[i]][2]]);
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,8) cin>>OX[i][0]>>OX[i][1]>>OX[i][2];
	FOR(i,6*6*6*6*6*6*6) {
		j=i;
		FOR(k,7) I[k+1]=j%6, j/=6;
		if(okok()) return;
	}
	_P("NO\n");
}

まとめ

判定をだいぶ長く書いてしまったけど、どこまで簡単に書けるんだろう。