说明
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
提示
示例中的第四个测试用例可以击穿五个沙锤,如下所示。
由