Codeforces 44 D. Hyperdrive

問題

3次元空間にn個の惑星があり、
1番の惑星から宇宙船が飛び立つ。

宇宙船は以下のような動きをする。

• 惑星から、他の全ての惑星に向かって一直線にn個の宇宙船が飛びたつ
• 他の惑星に着陸すると同時に他のn-2個の惑星に向かって宇宙船が飛び立つ
• 更にそれが他の惑星に着陸したら同様に動く

このとき、宇宙船二つが最初に衝突するまでにかかる時間を求めよ。
宇宙船は等速直線運動するものとする。

制約条件

n≦5000

方針

宇宙船が正面衝突するというのは、
1番の惑星とi番の惑星とj番の惑星を結ぶ三角形ができるということで、
最初に衝突するのは、宇宙船が周の一番短い三角形を飛ぶ時間の半分に等しい。

n≦5000なので、1番の惑星を含む三角形は全列挙できる。

ソースコード

double d3(int x,int y,int z){
	return sqrt(x*x+y*y+z*z*1.0);
}
void run()
{
	int n; cin>>n;
	vi x(n),y(n),z(n);
	rep(i,n)cin>>x[i]>>y[i]>>z[i];
	rep(i,n-1)x[i+1]-=x[0], y[i+1]-=y[0], z[i+1]-=z[0];
	
	double ans=INF;
	for(int i=1;i<n;i++)for(int j=i+1;j<n;j++)ans=min(ans,
		d3(x[i],y[i],z[i])+d3(x[j],y[j],z[j])+d3(x[i]-x[j],y[i]-y[j],z[i]-z[j]));
	printf("%.9f\n",ans/2);
}