P7133 Little P’s Starry Sky

>Stars lean on cloudy islets, splashing softly; dew drops like jade, trickling gently; on the jeweled steps, sorrowful orchids are cut one by one. The blue sky is like plain silk; light shakes the Big Dipper, crossing the sky. > >— Meng Fang (Yuan Dynasty), *Tianjingsha · Stars Lean on Cloudy Islets* Little P strolls under the starry sky. “Pick down the stars and give them to you, and you are my whole world.” “Tonight, I do not care about humanity; I only miss you.”

Treat the starry sky as a 2D Cartesian coordinate system. Little P is at $(0,0)$, i.e., the origin. There are $n$ stars in the sky, and the coordinates of the $i$-th star are $(x_i, y_i)$. Little P initially faces the point $(1,0)$. Then Little P will rotate in place $m$ times. After the $i$-th rotation, he will face the point $(u_i, v_i)$. He may choose to rotate counterclockwise or clockwise. Once he is facing the final direction of this rotation, the rotation stops immediately. He believes that, during the rotation, the more stars that appear right in front of him, he [data removed]. Little P wants to know, during each rotation, what is the maximum number of stars that can appear right in front of him (including the stars seen directly in front of him at the initial direction and at the ending direction of the rotation).

There are $n + m + 1$ lines in total. The first line contains two positive integers $n, m$, representing the number of stars and the number of rotations. The next $n$ lines each contain two integers $x_i, y_i$. The next $m$ lines each contain two integers $u_i, v_i$, with the meaning described in the Description. In each line, the two numbers are separated by a single space. The input uses Linux line endings, and there are no extra spaces at the end of any line.

Output $m$ lines, each containing one integer. The integer on line $i$ is the answer for the $i$-th rotation.

The illustration for Sample 1 is as follows:  Orange points are stars, and the green ray is Little P’s direction during the first rotation. In the first rotation, he turns from $(1,0)$ to $(-1,1)$. If he rotates clockwise (the blue region, including the boundary), the stars on $(1,0)$ and $(-2,-1)$ are counted, for a total of $2$ stars. If he rotates counterclockwise (the green region, including the boundary), the stars on $(1,0)$, $(1,1)$, $(2,2)$, and $(-1,2)$ are counted, for a total of $4$ stars. In the second rotation, he turns from $(-1,1)$ to $(-1,2)$. Rotating counterclockwise, all $5$ stars will appear right in front of Little P during the rotation.  Except for test points $24$ and $25$, all other test points guarantee that the absolute value of every coordinate is $\le 1000$. For the first $12$ test points, it is guaranteed that on any ray from the origin to any star, there is no other star. Except for test points $23$ and $25$, for all test points with odd indices, it is guaranteed that there are no stars on Little P’s initial facing direction and on each target direction. Except for test points $22$ and $24$, for all test points with even indices, it is guaranteed that there is at least one star on Little P’s initial facing direction and on each target direction. For $100\%$ of the data, it is guaranteed that all star coordinates are pairwise distinct, no coordinate equals $(0,0)$, and the initial direction of a rotation is never equal to the ending direction. Sample $3$ satisfies the constraints for even-indexed test points. Translated by ChatGPT 5