P9610 [CERC2019] Deep800080

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[Deep800080](https://contest.felk.cvut.cz/19cerc/solved/deep.pdf)”.**

The owner of the ship Deep800080, Ian, will have a barbecue on the lake tonight. There is a narrow straight pier that extends from the shore out into the lake. Ian thinks it is a good idea to have the barbecue at some point on the pier. He wants to test his new special barbecue charcoal. When it burns, it produces a unique deep purple smoke that spreads over the water surface. The smoke is guaranteed to form a perfect circle around the barbecue site. Eventually, the cloud will reach a certain maximum radius and then remain unchanged for the rest of the night, until it dissipates later. Several boats are anchored on the lake at different distances from the pier. Ian wants to notify their crews about the barbecue. Since he is a bit lazy, he hopes the barbecue smoke can do this job for him. Ian wants the crews to smell the smoke when the cloud reaches a boat, so they will immediately know there is a barbecue nearby. Ian wants to maximize the number of alerted crews, so he wants to choose a location on the pier to place the grill that maximizes the number of boats that the purple smoke can reach. You may assume the boats on the lake are firmly fixed, i.e., they will not move while the smoke layer is on the lake. Also, once the barbecue location is chosen, it stays fixed throughout the event.

The first line contains four integers $N, R, A, B\ (0\le N\le 3\times 10^5; 1\le R\le 10^6)$. $N$ is the number of boats on the lake, and $R$ is the maximum radius of the purple barbecue smoke. You may assume the pier is narrow and long, so it can be treated as a straight line passing through two distinct points with coordinates $(0, 0)$ and $(A, B)$. The next $N$ lines each contain two integers $X$ and $Y$, describing the coordinates of a boat on the lake. No two boats share the same coordinates. All coordinates use the standard Cartesian coordinate system on a plane, and their absolute values are at most $10^6$.

Output one integer, the maximum number of boats that the purple barbecue smoke can reach. A boat is considered reached if its position lies inside the circle formed by the smoke, including the boundary. You may assume that increasing the maximum radius of the smoke by $10^{-3}$ will not change the solution.

### Sample Explanation  Translated by ChatGPT 5