Circle and Points --- 2004年 愛媛大会 国内予選 問題D

【問題】
 xy平面上にN個の点が与えられる.半径1の円をxy平面上で動かして,それらの点をなるべくたくさん囲むようにする.このとき,最大でいくつの点を同時に囲めるかを答えなさい.ここで,ある円が点を「囲む」とは,その点が円の内部または円周上にあるときをいう.
 イラストは こちら

【入力】
 入力にはいくつかのデータセットが並び,最後に'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

Comments are closed.

Post Navigation