Round 3 500 - TheChroniclesOfAmber

問題

n 個の点がスタート地点からゴール地点へ速度 1 で移動する．移動の途中で各点は他の点が居る位置へワープすることができる．全点がゴール地点へ到達するのにかかる最小時間はいくつか？

考え方

wikipedia:三角不等式があるので，ワープは移動途中で行うよりも全部スタート時に行うのが良い．ただし，最初にワープする点が居た位置へは他の点はワープできないが，他はワープを行う順番をキチンとすれば任意に入れ替え等行うことができるので，その点だけ考慮して点同士を入れ替えてあとは目的地へ移動する時間を測れば良い．

ソース

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class TheChroniclesOfAmber
{
public:
  double minimumTime(vector<int> pX, vector<int> pY, vector<int> dX, vector<int>dY)
  {
    const int n = pX.size();
    vector< vector<double> > dist(n, vector<double>(n));
    for( int i = 0 ; i < n ; ++i )
      for( int j = 0 ; j < n ; ++j ) dist[i][j] = hypot(pX[i]-dX[j], pY[i]-dY[j]);

    double ret = 0;
    for( int i = 0 ; i < n ; ++i ) ret = max(ret, dist[i][i]);
    for( int i = 0 ; i < n ; ++i ) {
      double t = 0;
      for( int j = 0 ; j < n ; ++j ) {
        double d = 1e+19;
        for( int k = 0 ; k < n ; ++k )
          if( i != k ) d = min(d, dist[k][j]);
        t = max(t, d);
      }
      ret = min(t, ret);
    }
    return ret;
  }
};