P10459 Raid

《算法竞赛进阶指南》给出参考代码可以在本题获得 Subtask1 中的 44 分，在部分边界条件 $n=1,2$ 下会失分。该参考代码会被特意构造的数据卡掉，无法通过所有测试点。

在连续的对抗联盟失败后，帝国撤退到了最后的要塞。依靠其强大的防御系统，帝国击退了联盟的六波攻击。经过几个不眠之夜的思考，联盟将军亚瑟注意到防御系统唯一的弱点是其能源供应。该系统由 $N$ 个核电站供电，破坏其中任何一个都会使系统失效。 将军很快派出了 $N$ 名特工突袭这些电站，他们被空投到了要塞内。不幸的是，由于帝国空军的袭击，他们未能着陆到预期的位置。作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排计划。他现在想知道的第一件事是，哪个特工距离任何一个电站最近。作为首席官员，你能帮助将军计算特工与电站之间的最小距离吗？

第一行是一个整数 $T(1\leq T\leq 10^5)$，表示测试用例的数量。 每个测试用例以一个整数 $N (1 \leq N \leq 10^5)$ 开始。 接下来的 $N$ 行描述了电站的位置。每行包含两个整数 $X (0 \leq X \leq 10^9)$ 和 $Y (0 \leq Y \leq 10^9)$，表示电站的位置。 接下来的 $N$ 行描述了特工的位置。每行包含两个整数 $X (0 \leq X \leq 10^9)$ 和 $Y (0 \leq Y \leq 10^9)$，表示特工的位置。 保证在一个测试点中，$\sum N\leq 10^5$。

对于每个测试用例，输出距离最小值，保留三位小数，单独占一行。

翻译来自 ChatGPT。