#P9610. [CERC2019] Deep800080

[CERC2019] Deep800080

题目背景

题目译自 CERC 2019Deep800080

题目描述

Deep800080 的船主 Ian 今晚将在湖上烧烤。有一个狭窄的直码头,从岸边一直延伸到湖中。Ian 认为在码头的某个地点做烧烤是个好主意。

他想测试一下他的新型特制烧烤炭。当它燃烧时,会产生一种独特的浓紫色烟雾,弥漫在水面上。烟雾保证会在烧烤场周围形成一个完美的圆圈。最终,云层将达到一定的最大半径,并在晚上剩下的时间里保持不变,直到更晚的时候消散。

湖中离码头不同距离的位置停泊着多艘船只。Ian 想把烧烤的事通知他们的船员。由于有点懒,他希望烤肉烟雾能帮他做这项工作。Ian 希望,当云层到达一艘船时,船员们能闻到烟雾,这样他们就能立即知道附近有烧烤。

Ian 想最大化被警报的船员数量,因此他想在码头上选择一个可以最大化紫色烟雾到达的船只数量的地点放烧烤架。

你可以认为湖面上的船只已经牢牢地固定住了,即当烟雾层在湖面上时它们不会移动。此外,一旦选择了烧烤地点,其位置在整个活动中保持不变。

输入格式

第一行包含四个整数 $N, R, A, B\ (0\le N\le 3\times 10^5; 1\le R\le 10^6)$。NN 是湖面上的船只数量,RR 是紫色烧烤烟雾的最大半径。你可以认为桥墩又窄又长,因此可以将其视为穿过坐标为 (0,0)(0, 0)(A,B)(A, B) 的两个不同点的直线。

接下来 NN 行,每行都包含两个整数 XXYY,用于描述湖上一艘船的坐标。没有两艘船的坐标相同。

所有坐标都是平面中常见的 Cartesian 坐标,它们的绝对值最多为 10610^6

输出格式

输出一个整数,代表紫色烧烤烟雾可以到达的船只的最大数量。

如果船的位置在烟雾形成的圆圈内,包括其边界,则视为已到达。你可以认为将烟雾的最大半径增加 10310^{-3} 不会改变解决方案。

7 5 0 1
-1 -1
1 -1
0 0
2 3
3 4
10 10
2 12

5

3 1 1 0
0 0
2 0
4 0

2

4 1 1 0
0 0
1 1
1 -1
2 0

4

提示

样例解释