题解：P10459 Raid

THUPOST_REMAKE · 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，因此：

最终的时间和空间复杂度均为 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 处理距离开根。