Hide

Problem K
Meteor Observation

/problems/meteorobservation/file/statement/en/img-0001.jpg
Observing meteors through a fixed telescope

In a distant galaxy, a swarm of meteors is visible from your space station. Mission control has equipped you with a high-powered telescope that can rotate freely but has a limited field of view. Your telescope is fixed at a given position on a suitably aligned, but only two-dimensional $(x, y)$ coordinate plane.

Initially, the telescope points directly east. You can rotate it by any angle, but its field of view is fixed at $\theta $ degrees. Your task is to determine the maximum number of meteors that can be observed simultaneously by optimally choosing the telescope’s orientation.

A meteor is considered visible if the angle between the telescope’s viewing direction and the line from your telescope’s position to the meteor is within $\pm \theta /2$ degrees.

Input

The first line contains an integer $N$ ($1 \leq N \leq 200\, 000$), the number of meteors. Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$), representing the coordinates of each meteor. No two meteors will be at the same position. The following line contains two integers representing the $(x_t, y_t)$ coordinates of the telescope ($-10^9 \leq x_t, y_t \leq 10^9$), which is different from the position of any meteor. The last line contains a real number $\theta $ ($0.001 \leq \theta \leq 360$), representing the telescope’s field of view in degrees with up to 3 decimal places.

Output

Print a single integer representing the maximum number of meteors that can be observed at once. You are guaranteed that the answer does not change if $\theta $ were increased or decreased by $0.001$ degrees.

Sample Input 1 Sample Output 1
10
0 100
100 0
-100 0
0 -100
50 50
-50 -50
75 -75
-75 75
25 -25
-25 25
4 4
45
3

Please log in to submit a solution to this problem

Log in