← 返回题目列表

AtCoder · joisc2008_belt

belt. 腰带

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

ベルト (Belt) - 原题 PDF 第 1 页
原题PDF第5页
ベルト (Belt) - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Belt: ベルト


input ファイル“belt.in”
output 標準出力
ソースファイルbelt.c/belt.cpp
時間制限10.0 秒/ データ



  JOI 市では市の端から端まで一直線状に延びる動く歩道を建設することにした. 市の調査に

よると, 住民は自分の家から動く歩道までの距離がd 以内であれば市内の移動が便利になるた

め満足するが, d より大きいと満足しない. 市では, なるべく多くの住民を満足させるには, 動く

歩道の位置と方向をどうすれば良いかを知りたい. すべての住民の家の位置が与えられたとき,

動く歩道を最適な位置と方向で建設したときに満足する住民の数を求めるプログラムを書け.

 この問題では, 住民の家はすべて平面上の点であるとし, 動く歩道自体の幅はゼロと考えるこ

とにする. 動く歩道は住民の家を通ってもよく, その場合も住民は満足する.


Input. 入力ファイルの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 以下の任意の実数

に変えても, 満足する住民の数の最大値が変わらないようになっている.


Output. 出力は,標準出力に行うこと.出力は1 行からなる. その行には, 満足する住民の数

の最大値を出力せよ.

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





                          ベルト–1/2

例
 belt.in  標準出力
 10 8.000  9
 -2 1
 -10 2
 -2 3
 -7 -8
 7 5
 10 -5
 -9 -6
 -6 10
 -5 8
 4 -2





                          ベルト–2/2