| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 1024 MB | 7 | 1 | 1 | 100.000% |
JOI 市では市の端から端まで一直線状に延びる動く歩道を建設することにした. 市の調査に よると, 住民は自分の家から動く歩道までの距離が d 以内であれば市内の移動が便利になるた め満足するが, d より大きいと満足しない. 市では, なるべく多くの住民を満足させるには, 動く 歩道の位置と方向をどうすれば良いかを知りたい. すべての住民の家の位置が与えられたとき, 動く歩道を最適な位置と方向で建設したときに満足する住民の数を求めるプログラムを書け.
この問題では, 住民の家はすべて平面上の点であるとし, 動く歩道自体の幅はゼロと考えるこ とにする. 動く歩道は住民の家を通ってもよく, その場合も住民は満足する.
入力ファイルの 1 行目には, 住民の人数 n と市の調査によってわかった距離 d が空白 区切りで書かれている. d は正の実数である. 続く n 行には 二つの整数 xi と yi が空白区切り で書かれており, それぞれ住民の家の位置の x 座標と y 座標を表している. n 個の点はすべて 異なる.
d は小数点以下 3 桁まで書かれている可能性がある. 1 ≤ n ≤ 1, 000, 0.001 ≤ d ≤ 10, 000, −1, 000 ≤ xi, yi ≤ 1, 000 である.
サンプルデータと採点用データでは, d の値を d − 0.0005 以上 d + 0.0005 以下の任意の実数 に変えても, 満足する住民の数の最大値が変わらないようになっている.
出力は,標準出力に行うこと.出力は 1 行からなる. その行には, 満足する住民の数 の最大値を出力せよ.
10 8.000 -2 1 -10 2 -2 3 -7 -8 7 5 10 -5 -9 -6 -6 10 -5 8 4 -2
9