TopCoder SRM300 Div2 250Pts

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

タクシーキャブ距離というのは、軸に平行に移動するという制約下で2点間を移動する距離である(注：普通はマンハッタン距離の方がしっくりくる表現だと思います)。タクシーキャブ距離というのは、通常は二点を直線で結ぶよりも長い距離になる。タクシーキャブ距離と長方形領域の制約が与えられたとき、直線距離(=ユークリッド距離)の最大値を知りたい。maxX、maxYという長方形のX、Y値の最大値とtaxiDisというタクシーキャブ距離が与えられたときに、領域内の2点間でタクシーキャブ距離がtaxiDisになるもののうち、直線距離が最大になるときのその値を返せ。もし、領域内でtaxiDisになる2点の組がないなら-1.0を返せ。なお、長方形領域は0<=X<=maxX、0<=Y<=maxYを満たす領域である。

例えば、maxX=10、maxY=3、taxiDis=3とすると、3.0が解になる。2点間をX軸方向、あるいはY軸方向に平行に3移動するのが直線距離を最大にするからである。

私の解答はこちら。

public class Taxi {

 public double maxDis(int maxX, int maxY, int taxiDis) {
  if( maxX + maxY < taxiDis ) return -1.0; // 収まらない
  if( maxX >= taxiDis || maxY >= taxiDis ){ // 1辺に平行な状態で収まる
   return taxiDis;
  }else{ // XY軸とは平行にならない方向に直線が収まる
   double longer = maxX>=maxY ? maxX : maxY;
   double shorter = taxiDis - longer;
   return Math.sqrt(longer*longer+shorter*shorter);
  }
 }

}

得点は214.37/250、中央値は約149点。この問題のポイントは直線間距離を最大にするというのは、できるだけ1つの軸方向への移動距離を長くして、もう一つの軸に沿った移動は短くするということである。それに気付いたため、中央値より良い点数になったのだと思われる。コードもすっきりしていて読みやすくなった。