ACM International Collegiate Programming Contest
Japan Domestic, 2004-07-02
xy平面上にN個の点が与えられる．半径1の円をxy平面 上で動かして，それらの点をなるべくたくさん囲むようにする．このとき，最 大でいくつの点を同時に囲めるかを答えなさい．ここで，ある円が点を「囲む」 とは，その点が円の内部または円周上にあるときをいう．
Fig 1. Circle and Points
入力にはいくつかのデータセットが並び，最後に'0'一文字だけからなる行で 終わる．各データセットは整数一つを含む行で始まり，そのデー タセットに含まれる点の個数Nを与える．その後，点の座標を記述する N行が続く．その各行は，点のx座標 およびy座標を記述する二つの小数XとYからなる． 座標は小数点以下5桁で与えられる．
1 <= N <= 300, 0.0 <= X <= 10.0, および0.0 <= Y <= 10.0と仮定してよい．二つの点の距離が0.0001より近くなることはない．二つの点 の距離がほぼ2.0になることもない．より正確には，一つのデータセット中の 任意の2点間の距離dが1.9999 <= d <= 2.0001を満たす ことは決してない．最後に，一つのデータセット中の三つの点が，半径1の円周に， ともに非常に近くなることはない．より正確には，一つのデータセット中の任 意の3点をP1, P2, P3とし，xy-平 面上のある点からそれぞれへの距離をd1, d2, d3とする．このとき，0.9999 <= di <= 1.0001 (i = 1, 2, 3)が同時に成り 立つことは決してない．
それぞれのデータセットに対して，データセット中の点で，半径1の円一つ で同時に囲むことができる点の最大数を出力しなさい．それ以外の文字は， 先頭や末尾の空白を含め，出力してはならない．
3 6.47634 7.69628 5.16828 4.79915 6.69533 6.20378 6 7.15296 4.08328 6.50827 2.69466 5.91219 3.86661 5.29853 4.16097 6.10838 3.46039 6.34060 2.41599 8 7.90650 4.01746 4.10998 4.18354 4.67289 4.01887 6.33885 4.28388 4.98106 3.82728 5.12379 5.16473 7.84664 4.67693 4.02776 3.87990 20 6.65128 5.47490 6.42743 6.26189 6.35864 4.61611 6.59020 4.54228 4.43967 5.70059 4.38226 5.70536 5.50755 6.18163 7.41971 6.13668 6.71936 3.04496 5.61832 4.23857 5.99424 4.29328 5.60961 4.32998 6.82242 5.79683 5.44693 3.82724 6.70906 3.65736 7.89087 5.68000 6.23300 4.59530 5.92401 4.92329 6.24168 3.81389 6.22671 3.62210 0
2 5 5 11
ここに1番目のデータがある．
The ACM ICPC