belt - ベルト (Belt) Editorial /

Time Limit: 10 sec / Memory Limit: 64 MiB

AtCoder での提出方法

標準入力から入力を読み込み,標準出力へ出力すること.

配点 : 100 点

問題文

JOI 市では市の端から端まで一直線状に延びる動く歩道を建設することにした. 市の調査によると, 住民は自分の家から動く歩道までの距離が d 以内であれば市内の移動が便利になるため満足するが, d より大きいと満足しない. 市では, なるべく多くの住民を満足させるには, 動く歩道の位置と方向をどうすれば良いかを知りたい. すべての住民の家の位置が与えられたとき,動く歩道を最適な位置と方向で建設したときに満足する住民の数を求めるプログラムを書け.

この問題では, 住民の家はすべて平面上の点であるとし, 動く歩道自体の幅はゼロと考えることにする. 動く歩道は住民の家を通ってもよく, その場合も住民は満足する.

入力

入力ファイルの 1 行目には, 住民の人数 n と市の調査によってわかった距離 d が空白区切りで書かれている. d は正の実数である. 続く n 行には二つの整数 x_{i} と y_{i} が空白区切りで書かれており, それぞれ住民の家の位置の x 座標と y 座標を表している. n 個の点はすべて異なる.

d は小数点以下 3 桁まで書かれている可能性がある. 1 \leqq n \leqq 1, 000, 0.001 \leqq d \leqq 10, 000, -1, 000 \leqq x_{i}, y_{i} \leqq 1, 000 である.

サンプルデータと採点用データでは, d の値を d - 0.0005 以上 d + 0.0005 以下の任意の実数に変えても, 満足する住民の数の最大値が変わらないようになっている.

出力

出力は,標準出力に行うこと.出力は 1 行からなる. その行には, 満足する住民の数の最大値を出力せよ.

採点基準

採点に用いる入力データのうち,配点の 60\% 分は 1 \leqq n \leqq 100 をみたす.

入力例 1

10 8.000
-2 1
-10 2
-2 3
-7 -8
7 5
10 -5
-9 -6
-6 10
-5 8
4 -2

出力例 1

9

Source Name

JOI 2007-2008 春季トレーニング合宿 Contest Day2