新規
編集
添付
時間制限:5000ミリ秒
メモリ制限:30000KB
ケース別時間制限:2000ミリ秒
円と点
問題 
xy平面にN個の点が与えられる。あなたは半径1の円が与えられ、できるだけ多くの点を含むようにこれを動かす。いちどに含むことのできる最大の点の数を答えよ。円の内部または円周上に点があるとき、円は点を含むとする。
入力
入力はいくつかのデータセットの列からなり、そのあとに入力の終わりを意味する1つの整数'0'を含む行が続く。各データセットの最初の行はデータセット内の点の数を意味する整数Nを含む。続くN行にはそれぞれの点の座標が書かれている。各行は10進小数XとYが書かれていて、それぞれ点のx座標とy座標を意味する。小数点以下5桁まで与えられる。
1<= N <= 300, 0.0 <= X <= 10.0, 0.0 <= Y <= 10.0としてよい。2つの点の間の距離が0.0001より小さくなることはない。2つの点の間の距離がおよそ2.0、つまり1.9999以上2.0001以下、になることはない。それから、どの3つの点も1つの半径1の円に近いことはない。つまり、データセット内のいかなる3点P1,P2,P3と、xy平面上のいかなる点についても、その点からP1,P2,P3までの距離d1,d2,d3が全て0.9999以上1.0001以下になることはない。
出力
各データセットについて、半径1の円が一度に含むことのできる点の数の最大値を含む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
出典
Japan 2004 Domestic
