← 返回题目列表

AtCoder · fuka_iru

F. 伊鲁对阵萨基

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

说明

2D 平面上的马拉卡斯(点) 有n。 我想用 Buster 射出尽可能多的沙球。 Buster 宽度为 2w,具有无限长矩形的大小,并且从原点发射,使得原点穿过矩形宽度的中心。 回答如果确定了发射破坏器的适当角度,则可以射穿沙球的最大数量。

输入

输入由多个测试用例组成。输入的结尾由仅包含两个零的行指示。 每个测试用例均按以下格式给出。

n w
x_1 y_1
…
x_n y_n
  • 1≦n≦100,000
  • 1≦w≦1,000
  • 0≦x_i,y_i≦100,000

测试用例的第一行包含两个整数 写入n,w。 n代表沙球数量,w表示破坏者的半径。

继续 来自行n每行包含两个整数 表示第x_i,y_i。 x_i,y_i是 由于它被视为i个沙球的坐标。

两个测试用例之间有一个空行。

w的±10^{-6}保证即使你改变答案也不会改变。 每个文件的测试用例数量保证少于 1,000 个。 另外,对于每个文件n的总和保证小于或等于 300,000。

输出

对于每个测试用例,在一行上打印可以击穿的沙球的最大数量。

示例输入

1 1
2 2

4 1
3 3
4 4
5 5
6 6

3 2
1 1
2 1
3 1

7 3
10 3
10 5
10 7
10 9
10 11
10 13
10 15

2 1000
10 10
10 10

5 10
100 20
110 21
48 9
4 240
5 2012

0 0

示例输出

1
4
3
5
2
3

提示

示例中的第四个测试用例可以击穿五个沙锤,如下所示。 由 画像はイメージです.実際と異なる場合がございます.