25109번 - Radar 스페셜 저지다국어

We are using a special radar to scan an area. The radar accepts a list of distances, e.g. $2$, $4$, $1$, and a list of angles, e.g. $100^◦$, $270^◦$, $180^◦$, $10^◦$, $300^◦$, and scans the points across all the given distances and angles. How close to some other points of interest will we be able to scan?

The first line of the input gives three space-separated integers: $R$, $F$, $N$, representing the number of radii, the number of angles, and the number of points of interest, respectively. Then $R$ lines follow, $i$-th of which contains an integer $r_i$, representing the distance from the radar that will be scanned. Then, $F$ lines follow, each containing two space-separated integers $(f_x)_i$, $(f_y)_i$, that represent Cartesian coordinates of a point, defining the $i$-th angle. Then, $N$ lines follow, each containing two space-separated integers $x_i$, $y_i$, that represent the Cartesian coordinates of the $i$-th point.

The angle, defined by the point $(f_x)_i$, $(f_y)_i$ is the angle from the $x$-axis to the ray from the origin through $(f_x)_i$, $(f_y)_i$.

Output $N$ lines, $i$-th of which should contain the distance from the point $(x_i , y_i)$ to the closest scanned point. The result will be considered correct if it is within the $10^{-6}$ of absolute or relative precision.

• $1 ≤ R, F, N ≤ 10^5$
• $|x_i|, |y_i|, |(f_x)_i|, |(f_y)_i|, r_i < 10^6$
• $(f_x)^2_i + (f_y)^2_i , r_i > 0$
• All $r_i$ are pairwise distinct.
• Rays, defined by $(f_x)_i$,$(f_y)_i$, are pairwise distinct.

Illustration of sample case: