自动搬运

查看原文

来自洛谷，原作者为

	THUPOST_REMAKE 清华研究生资格机试洛谷题单id：711612

搬运于2025-08-24 22:58:09，当前版本为作者最后更新于2025-07-20 21:34:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题解不介绍 Voronoi 图的具体做法，只会提供题目思路（基本等同于本讨论区的详细解读版）、一些参考资料以及本题需要处理的一些坑点。

题意

给定 $n$ 个白色点和 $m$ 个黑色点，求出所有一白一黑的点对中的最小欧氏距离。本题中 $n=m\le 10^5$，多测。

思路

由于本题的点分为两类，因此原本适用于平面最近点对的分治无法做，会退化到 $O(n^2)$。

直接对白色点建立 kd-tree，然后对所有黑色点做最近邻查询的做法也不可行，因为欧氏最近邻查询的最坏复杂度还是 $O(n)$，只需要构造近似于圆的点集就能轻松卡掉。

通过查阅上述讨论区，我们得知本问题为双色最近点对（Bichromatic Closest Pair, BCP）问题，且在查阅相关论文时可以发现本问题与欧几里得最小生成树（EMST）可在任意维度下进行规约，本题所涉及的 2 维平面属于相对简单的情形。

对于以上两个问题，先对所有点构成的点集构造 Delaunay 三角剖分，并利用最左转线法求出其对偶图，即 Voronoi 图。以上两个过程均可在 $O(n\log n)$ 完成，其中 $n$ 为点集规模。

由于 Voronoi 图为平面图，根据欧拉公式，边数不超过 $3n-6$，因此：

• 对于 EMST 问题，直接利用所有边做最小生成树即可。
• 对于 BCP 问题，直接在 Voronoi 图中找到相邻点对异色的边中长度最短的即可。

最终的时间和空间复杂度均为 $O(n\log n)$ 的，常数稍微有一点大。

评测以及坑点

对于 Voronoi 图的正确性，可能需要多找几个评测链接分别测一测。

EMST 相关的：

• luogu P1265：暴力可过，可以写个 Prim 用作对拍
• luogu P6362：EMST，近期数据进行了一波大加强
• Library Checker - Euclidean MST：数据强度也比较强，但是造题人的 std 也被上述 luogu 新上的数据给 hack 掉了（笑）。本链接要输出具体解，需要考虑的退化情况较多，建议是上面几个都测一下。

本题相关的：

• luogu P10459，时限 2s，我的实现是 1.6s 左右过的。
• luogu U582951，时限 5s。
• AcWing 119，上面有用户提供的零散 Hack 数据，但是本链接前空间限制只有 64 MB，目前已提交工单申请改至 512 MB。测了一下应该也没别的问题。

需要处理的坑点如下：

• 多测处理很恶心，这个不赘述。
• 可能存在共点、共线的退化情况，有一些 Voronoi 图的实现在共线情况下会出错（比如我的），需要特判。这个情况求最近点对也比较简单。
• double 能表示的精度比 long long 要低，本题的测试点 6 就会卡这个，因此需要使用 long double 和 sqrtl 处理距离开根。

参考资料

• 本题讨论区
• OI Wiki Delaunay 三角剖分/Voronoi图
• 邓俊辉《数据结构》 习题 6-3 以及 6-32