TopCoder SRM266 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

2つの飛び乗れる石がある10フィートの川を渡りたいと思っている。何回かジャンプが必要になるが、興味があるのは、一番長い距離のものだけである。これは明らかに大事な問題で、できるだけ飛ぶ距離の最大値を小さくしたいと思っている。二つの石の距離はユークリッド距離で定義する。
さて、整数型のx[]とy[]という2つの要素を持つ配列が与えられる。(x[i]、y[i])はi番目の石の座標を表している。あなたははじめ、x座標が0で、y座標は任意の値を取り得る川岸にいる。反対側の岸はx座標が10でy座標は任意の値を取る川岸である(つまり、川はy軸に平行なものと考え、その中に石が二つ置かれているということになる)。
あなたが飛ばなければならない最大距離をもっとも近い整数値に丸めて返せ。なお、石はx座標の1～9の整数値、y座標の0～10の整数値の場所にあるものとする。また、二つの石は同じ場所にはないものとする。

私の解答はこちら。

// 石1 -> 石2 -> 対岸
// 石1 -> 対岸
// 石2 -> 石1 -> 対岸
// 石2 -> 対岸
// 以上の4パターンを飛ぶ順番として列挙しておけばよい。以下のコードでは上から順に0～3という
// 添字を割り当てて、各ケースにおける飛ばなければならない距離の最大値を計算している。
public class SwimmersDelight {
 public int longestJump(int[] x, int[] y) {
  double[] maxDist = new double[4];
  double distBetweenStones = Math.sqrt(Math.pow(x[0]-x[1],2)+Math.pow(y[0]-y[1],2));
  maxDist[0] = Math.max(x[0], distBetweenStones);
  maxDist[0] = Math.max(maxDist[0], 10-x[1]);
  maxDist[1] = Math.max(x[0], 10-x[0]);
  maxDist[2] = Math.max(x[1], distBetweenStones);
  maxDist[2] = Math.max(maxDist[2], 10-x[0]);
  maxDist[3] = Math.max(x[1], 10-x[1]);
  double max = 10;
  for( int i=0 ; i<4 ; i++ ){
   if( maxDist[i] < max ){
    max = maxDist[i];
   }
  }
  return (int)Math.round(max);
 }

}

得点は108.13/250。結局、全パターンを列挙して求めるのが一番早いようだ。提出者の正解率が3割程度ということから、結構難しい問題だったようだ。