Description

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

Input Format

输入的第一行包含三个用空格分隔的整数 $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$ 的射线的夹角。

Output Format

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

3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

0.977772290466
2.750120773895
0.846777708005
1.464071052924
0.585786437627

Hint

说明

样例的示意图如下：

:::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 翻译