TopCoder Open 2010 Round 3 Medium.TheChroniclesOfAmber

問題概要

王子達のそれぞれの初期座標と、目的地の座標が与えられる。

王子達は、他の王子の居る場所へ、好きなタイミングで一瞬でテレポートできるとき、全ての王子達がそれぞれの目的地へたどり着くのに必要な最小の時間を求めよ。

王子の数は50人以下である。

解法

王子Aが王子Bに合流するような場合を考える。
王子Bの道のりの途中で合流するなら、王子Aは王子Bのスタートで合流して、そこからまっすぐ自分の目的地へ向かったほうが早い。

よって全ての王子が誰のスタート地点からスタートすれば早いかを求めれば良い……のだが、
二人の位置を同時にスワップすることは出来ないので、「王子が一人もいなくなる地点」を全通りためしてみる。

ソースコード

vi px,py,dx,dy;
double D(int s,int t)
{
	return hypot(px[s]-dx[t],py[s]-dy[t]);
}
class TheChroniclesOfAmber {
	public:
	double minimumTime(vector <int> princeX, vector <int> princeY, vector <int> destinationX, vector <int> destinationY)
	{
		int n=princeX.size();
		px=princeX,py=princeY,dx=destinationX,dy=destinationY;
		
		double ans=0;
		rep(i,n)ans=max(ans,D(i,i));
		
		rep(i,n)
		{
			double t=0;
			rep(j,n)
			{
				double m=INF;
				rep(k,n)if(i!=k)m=min(m,D(k,j));
				t=max(t,m);
			}
			ans=min(ans,t);
		}
		return ans;
	}	
};