Fenomenalni Fenjer
InterviewTime limit1sMemory limit512 MB
Place a point on the x-axis so that a circle of radius r centered there covers as many of the n given points as possible, and print that maximum count.
- Level
Medium6 of 10
- Topics
- Geometry, Sorting, Sliding window, Two pointers
- Solved
- No attempts yet
Problem
In the small village of Cugovec Biškupečki live n residents, each in their own house. Unfortunately, super fast internet has not yet reached this part of the country, and the main reason is that no household has electricity. As a result, the residents of Cugovec Biškupečki do not spend their free time solving algorithmic problems on popular websites; they only come up with algorithms using paper and pencil. Of course, winter is the hardest time for them, since darkness falls early and they must solve problems in their heads because they can no longer see what they wrote on paper.
However, this winter they decided to put an end to their problem. One resident exclaimed that he owns a candle but cannot light it. Another resident replied that he owns a lighter, a third said he owns a lantern, and a fourth found a long pole just this morning. A brilliant plan was soon made: when darkness falls, they will put the lit candle into the lantern, mount the lantern on the pole, and drive the pole into the ground. All that remains is to decide where to place the pole.
Using methods of mathematics and computation, the residents concluded that the lantern will illuminate a circular area of radius r. They also agreed together to place the pole somewhere along the street that passes through Cugovec Biškupečki, in such a way that the light illuminates the maximum number of houses. Of course, they then placed the problem in a coordinate system, laying the street on the x-axis and determining the coordinates of each house.
Can you determine how many houses will be illuminated after the residents set up the lantern?
Note: A house is illuminated if it lies on the edge of or inside the circle of radius r centered at the lantern. The optimal position of the lantern is not necessarily at integer coordinates.
Input
The first line contains the natural numbers n (1 ≤ n ≤ 100 000) and r (1 ≤ r ≤ 10^9) from the problem statement.
The i-th of the following n lines contains two integers xi and yi (0 ≤ |xi|, |yi| ≤ 10^9) representing the coordinates of the house where the i-th resident lives. The positions of all houses are distinct.
Output
Print the requested number from the problem statement in a single line.