TopCoder SRM353 Div2 250Pts

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

(x1, y1)、(x2, y2)を焦点とする楕円で、2点の距離の和がdで与えられるとき、楕円の中に格子点(x,y座標が共に整数になる点)がいくつあるかを数えて返すメソッドを作成せよという問題である。

私の解答はこちら。

public class EllipseCoverage {

 public int calculateCoverage(int x1, int y1, int x2, int y2, int d) {
  int[] xrange = new int[2];
  int[] yrange = new int[2];
  // とりうる値の範囲を長方形状にしておく(計算量削減のため)
  xrange[0] = Math.min(x1, x2)-d;
  xrange[1] = Math.max(x1, x2)+d;
  yrange[0] = Math.min(y1, y2)-d;
  yrange[1] = Math.max(y1, y2)+d;
  int nInEllipse = 0;
  for( int i=xrange[0] ; i<=xrange[1] ; i++ ){
   for( int j=yrange[0] ; j<=yrange[1] ; j++ ){
    double dx1 = x1-i;
    double dx2 = x2-i;
    double dy1 = y1-j;
    double dy2 = y2-j;
    // 楕円の中というのは2点間の距離の和がd未満ということになる
    if( Math.sqrt(dx1*dx1+dy1*dy1) + Math.sqrt(dx2*dx2+dy2*dy2) < d){
     nInEllipse++;
    }
   }
  }
  return nInEllipse;
 }

}

得点は229.53/250、中央値は約162点。1回のsubmitでシステムテストクリア。実際には焦点の座標は-100～100の整数値しかとらないので、全探索でも解けるのですが、規模が大きくなる場合は探索範囲を絞るのがコツに思います。上のコードでは取り得るx,yの値の範囲を計算して、求める点がすべて含まれる小さな長方形の形状にし、範囲を絞って全探索しました。コーディングでは、<= dとして少し嵌ってましたが、問題文をよく読んで解決しています。