UVa 10136 : Chocolate Chip Cookies

問題リンク：http://uva.onlinejudge.org/external/101/10136.html

問題概要：
複数の点が与えられる
好きな場所に直径５cmの円を置いたときにその円の内部に入る点の数を最大化せよ

解法：
AOJ1132やAOJ0090と同じ問題
円の半径が2.5になっただけ

ある2点を決めた時、その2点を円周上にもつ円は２つ存在する
すべての2点の組み合わせについてその円を作れば、そのどれかが
最も点を多く含む円のうちの１つである

点を一番多く含む円について考える
その円を内部にある点の数が変わらないように適当に動かす
この時その円を少なくとも２つの点を円周上にもつように移動できる
このことから全ての2点の組み合わせについて円をつくれば円の内部に
最も多く点を含む円のうちの１つを見つけることができることが分かる

実装方法は以下の通り
2点p1,p2を選ぶ
p1からp2に向けてベクトルをはる
そのベクトルの中心に垂直な線分は円の中心点をその線分上にもつ
p1,ベクトルの中心の点（以下 vm）、円の中心（以下 cm）からなる三角形を考える

p1からvmまでの距離は(p1とp2の距離)/2 (以下 len)
p1からcmまでの距離は円の半径と一致するので2.5 (5でない亊に注意！５は直径!!)
vmからcmまでの距離は分からないのでxとする
これは直角三角形となるので、
x = sqrt(2.5*2.5-len*len)
これでvmから円の中心までの距離がわかった
vmからベクトル(p2-p1)に垂直に+x,-xだけ進んだ点が円の中心である
後はループで円の中心との距離が2.5以下であるものを数え、最大のものを出力すれば良い

outputとoutputの間には改行が入ることに注意！！！

コード：

// Library - template - 略

void compute(const vector<Point> &vec)
{
  int ans = (int)(!vec.empty());
  int n = vec.size();
  const double radius = 2.5;
  rep(i,n)
    {
      REP(j,i+1,n)
	{
	  Point A = vec[i];
	  Point B = vec[j];
	  double y = abs(B-A)*0.5;
	  if(!equals(6.25-y*y,0.0) && (6.25-y*y) < 0.0)continue;
	  double x = sqrt(6.25 - y*y);
	  Point e = (B-A)/abs(B-A);
	  Vector mv = e * y;
	  Vector AtoB = e * x;
	  Point midpoint[2];
	  midpoint[0] = rotate(AtoB, toRad(90.0)) + mv + A;
	  midpoint[1] = rotate(AtoB,-toRad(90.0)) + mv + A;

	  rep(type,2)
	    {
	      int cnt = 0;
	      rep(k,n)
		{
		  double dist = abs(midpoint[type]-vec[k]);
		  if(equals(dist,radius) || dist < radius)
		    {
		      cnt++;
		    }
		}
	      ans = max(ans,cnt);
	    }
	}
    }

  cout << ans << endl;
}


int main()
{
  string line;
  int T;
  getline(cin,line);
  T = (atoi)(line.c_str());
  getline(cin,line);
  bool first = true;
  while(T--)
    {
      if(!first)cout << endl;
      first = false;
      vector<Point> vec;
      while(getline(cin,line))
	{
	  if(line.empty())break;
	  stringstream ss;
	  ss << line;
	  double x,y;
	  ss >> line;
	  x = (atof)(line.c_str());
	  ss >> line;
	  y = (atof)(line.c_str());
	  vec.push_back(Point(x,y));
	}
      assert(!vec.empty());

      compute(vec);

    }
  return 0;
}