TopCoder SRM 355 Div1 Medium Tetrahedron

問題

空間上に4点がある。
それぞれの距離がd[i][j]によって与えられる。

この距離を満たす4点は存在するか、するならYESを、しないならNOを答えよ。

制約条件

dは4行4列の対称行列
d[i][j]≦10

方針

一点は原点に固定してよい。
2点目はx軸上の正の部分に取ってよい。
3点目はxy平面上に取る。
連立方程式を解けば、3点目の座標(x[2],y[2])が求まる。

4点目の座標を(x[3],y[3],z[3])すると、連立方程式が3つ立つ。
連立方程式が正しい解を持てば、4点目の座標が具体的に求まり、4点が存在することがわかる。

ソースコード

inline double sq(double x){return x*x;}

class Tetrahedron {
	public:
	string exists(vector <string> dist) 
	{
		vector<vi> d(4);
		rep(i,4){
			stringstream ss(dist[i]);
			int x;
			while(ss>>x)d[i].pb(x);
		}
		double x[4],y[4],z[4];
		x[0]=y[0]=z[0]=0;
		x[1]=d[0][1]; y[1]=z[1]=0;
		
		x[2]=(sq(x[1])-sq(d[1][2])+sq(d[0][2]))/(2*x[1]);
		y[2]=sq(d[0][2])-sq(x[2]);
		if(y[2]<0)return "NO";
		y[2]=sqrt(y[2]);
		z[2]=0;
		
		x[3]=(sq(x[1])-sq(d[1][3])+sq(d[0][3]))/(2*x[1]);
		y[3]=(sq(y[2])-sq(d[2][3])+sq(d[0][3])+sq(x[3]-x[2])-sq(x[3]))/(2*y[2]);
		z[3]=sq(d[0][3])-sq(x[3])-sq(y[3]);
		if(z[3]<0)return "NO";
		z[3]=sqrt(z[3]);
		
		rep(i,4)rep(j,4)
		if(abs(sq(x[i]-x[j])+sq(y[i]-y[j])+sq(z[i]-z[j])-sq(d[i][j]))>EPS)
			return "NO";
		rep(i,4)cerr<<x[i]<<" "<<y[i]<<" "<<z[i]<<endl;
		
		return "YES";
	}
};