P13770 [CERC 2021] Radar

我们正在使用一种特殊的雷达扫描一个区域。该雷达接受一组距离（例如 $2, 4, 1$）和一组角度（例如 $100^\circ, 270^\circ, 180^\circ, 10^\circ, 300^\circ$），并会在所有给定的距离和角度上扫描点。我们能够扫描到距离某些感兴趣点最近的距离是多少？

输入的第一行包含三个用空格分隔的整数 $R$、$F$、$N$，分别表示半径的数量、角度的数量和感兴趣点的数量。接下来 $R$ 行，每行包含一个整数 $r_i$，表示将被扫描的距离。然后接下来 $F$ 行，每行包含两个用空格分隔的整数 $(f_x)_i$、$(f_y)_i$，表示一个点的笛卡尔坐标，用于定义第 $i$ 个角度。再接下来 $N$ 行，每行包含两个用空格分隔的整数 $x_i$、$y_i$，表示第 $i$ 个感兴趣点的笛卡尔坐标。 由点 $(f_x)_i, (f_y)_i$ 定义的角度是从 $x$ 轴到从原点经过 $(f_x)_i, (f_y)_i$ 的射线的夹角。

输出 $N$ 行，第 $i$ 行应输出点 $(x_i, y_i)$ 到最近被扫描点的距离。结果只要在绝对误差或相对误差 $10^{-6}$ 以内即可视为正确。

### 说明 样例的示意图如下： :::align{center}  ::: ### 输入范围 - $1 \leq R, F, N \leq 10^5$ - $|x_i|, |y_i|, |(f_x)_i|, |(f_y)_i|, r_i < 10^6$ - $(f_x)_i^2 + (f_y)_i^2, r_i > 0$ - 所有 $r_i$ 两两不同。 - 由 $(f_x)_i, (f_y)_i$ 定义的射线两两不同。 由 ChatGPT 4.1 翻译