Problem E. Extreme Image

时间限制 2000 ms   内存限制 256 MB

Mr. Potato Head is working now for the Universal Network of Astronomical Luminous bodies (UNAL). As his first work, he has to capture an image with the closest luminous bodies from earth and present the image to the UNAL.

However, the UNAL observatory cannot get the image for all distances and all angles, in fact, it only captures an image for an angular range of $$$\alpha$$$ degrees and a distance range of $$$d$$$ millions of kilometers.

Formally, given $$$x$$$ (millions of kilometers) and $$$\omega$$$ (degrees), the observatory can capture all luminous-bodies with a distance in the range $$$[x, x+d]$$$ and an angle in the range $$$[\omega, \omega + \alpha]$$$. The size of each luminous body is considered negligible.

Mr. Potato Head wants to get the best possible image from the observatory, in order to do so, he needs to get the image with the maximum number of luminous bodies he can.

Can you help him to achieve this goal?

输入数据

The first line of input contains 3 numbers: integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, integer $$$d$$$ $$$(1 \leq d \leq 10^5)$$$ and real $$$\alpha$$$ $$$(0.00 \leq \alpha < 360.00)$$$ $$$-$$$ The number of luminous bodies closest to earth, the distance range of the observatory in millions of kilometers and the angular range of the observatory in degrees, respectively.

Next $$$n$$$ lines contains the information of the location of the luminous bodies regarding to the earth. The $$$i$$$-th line consists of 2 numbers: integer $$$r_i$$$ $$$(1 \leq r_i \leq 10^5)$$$ and real $$$\omega_i$$$ $$$(0.00 \leq \omega_i < 360.00)$$$ $$$-$$$ The distance of the $$$i$$$-th luminous-body to the earth in millions of kilometers and its corresponding angle in degrees, respectively.

All the reals numbers on the input are up to 2 decimals.

输出数据

Output a single integer $$$-$$$ The maximum number of luminous bodies to capture in the observatory.

样例

提交

请先 登录

© 2025 FAQs Contact About