Problem K
Meteor Observation

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 |