浅谈平面网格化

· · 算法·理论

平面网格化就是找一个 L 然后把平面划分成若干 L\times L 的正方形，并利用其的一些性质进行操作。

其实就是整理了几道平面网格化相关的杂题。在整理之前我真没想到这个东西这么小众，尝试在网上搜索相关例题都搜不出来，所以来记录一下。

平面最近点对

给定平面上 n 个点，求欧几里得距离最小的一对点。

考虑随机重排之后按顺序加入所有点，动态维护任意时刻的最近距离。假设前 i 个点的最近点对距离为 d。

那么把平面分成若干 d\times d 的小正方形构成的网格，那么能够发现一个小正方形中只会有 O(1) 个点。那么第 i+1 个点加入的时候只需要其所在正方形周围的 3\times 3 范围内的正方形里的点即可。

如果答案更新了就需要重构正方形网格。我们可以将任意时刻答案的变化看做是一个随机排列的前缀 \min，而对于一个数 i，其是前缀 \min 当且仅当 1\sim i 中 i 最先出现，而显然其发生的概率为 \frac 1i，因此第 i 个点更新答案的概率是 \frac 1i，因此期望复杂度为 O(\sum i\times \frac 1i)=O(n)。

QOJ9776

有 n 个点，按顺序依次添加每个点并实时回答有多少个二元组 (i,j) 满足 j 同时是到 i 的曼哈顿距离最大的点和到 i 的切比雪夫距离最小的点。

记全局曼哈顿距离最大的两个点对答案为 L，那么根据三角不等式，任意一个点到其他点最大的曼哈顿距离都至少为 \frac L2，因此其对应切比雪夫距离也至少为 \frac L4。因此如果一个点到其他点的最小切比雪夫距离小于 \frac L4，它肯定没法作为一个合法的 i。注意这里 i,j 并不是对称的。

考虑将网格划分成若干大小为 \frac L4\times \frac L4 的块，不难发现一个能作为合法的 i 的点必然要满足所在块只有它一个点，而不难发现总共只有 O(1) 个块，因此每次计算答案可以直接枚举每一个块然后检查是否只有一个点。

于是现在还是有两个问题，一个是在加点过程中如何应对 L 的增大，一个是怎么对于每个 i 计算有多少个合法的 j。

先看前者，不难发现当我们实际划分的边长比 L 略小常数倍的时候，量级都是可以接受的。因此考虑每次新的 \frac L4 比当前边长大了一倍的时候重构整个网格。这样总重构次数为 \log，每次重构为线性。维护 L 也是简单的，直接把曼哈顿距离的两个绝对值拆成四种情况的 \max，分别维护即可。

再来看后者。我们希望动态维护出所有可以作为 i 的点到其他所有点的曼哈顿距离的 \max 和切比雪夫距离的 \min，并且记录有多少个点能同时取到这两个值。

如果一个数加入的时候就自己一个块，注意到每一次重构之后只会有 O(1) 这种情况的发生，所以总共只有 O(\log) 个这样的点，直接枚举前面所有点计算即可。

每次加入新点的时候让所有目前仍然可能作为 i 的点都对它更新一下距离，如果 \max 和 \min 中有任何一个值变化就把之前所有能同时取到这两个值的点都扔掉。

于是总复杂度 O(n\log V)。

因为这个题空间很小，所以存储每个块里的点数的时候不能用 umap 或者 map 之类的东西，需要直接坐标偏移一下然后用二维数组存。

P4631

平面上有 n 个圆。每次找出半径最大的圆，有多个就选择编号最小的，并删除它以及所有和它有交的圆（相交或相切），直到所有圆都被删除。你需要对每个圆求出它是被哪个圆删掉的。

假设当前最大圆半径为 R，那么将平面分成若干 2R\times 2R 的网格，显然每个圆只可能会与其所在网格周围 3\times 3 范围内格子里的圆相交，因此每次直接枚举范围内所有的圆然后删除即可。和上一题类似的，只要 R 达到了之前的一半就重构网格。

考虑枚举那一块的复杂度。对于一个点 P 以及一个网格对应的半径 B，显然只有在 P 周围 3\times 3 格子里并且半径在 \frac B4\sim \frac B2 之间的圆才可能会遍历到 P，而显然最多只会有常数个互不相交的这样的圆，因此在每一次重构之后每个点被访问的次数都是 O(1) 的。

于是总复杂度 O(n\log V)，细节需要精细实现。

CF1641F

给定 n 个在 [-10^8,10^8]^2 上随机生成的点 A_i 以及两个常数 k,l，你需要选择一个长度为 l 的子段以及一个圆使得这个子段中至少有 k 个点都被圆包含，最小化这个圆的半径。

考虑如果我们已经确定了 r，如何判定其是否合法。问题等价于找一个代表圆心的点 O 以及 k 个点 A_{i_1},A_{i_2},\dots,A_{i_k} 使得 i_k-i_1<l 且 O 到每个点距离都不超过 r。于是反过来改成若干半径相同的圆，你需要找到 k 个下标差不超过 l 并且有交的圆。

随便选取交的区域边界对应的任意一个圆 C，不妨要求 O 要在 C 的边界上，那么只需要考虑其他圆和 C 的交对应的那一段圆弧。如果我们得到了所有圆弧（可以看作区间），只需要扫描线即可判断是否合法。如果有 s 段圆弧，复杂度就是 O(s\log n)。

在具体开始分析 s 之前，先重新考虑一下答案的上界：

如果 r\ge\sqrt 2\times 10^8，那么显然每个点的圆都会覆盖到原点，因此一定是合法的。

如果 r<\sqrt 2\times 10^8，如果想要不合法那么每个点至多只能被覆盖 k-1 次，于是所有圆和 [-10^8,10^8]^2 的交的面积之和不能超过 10^{16}(k-1)，而因为 r<\sqrt 2\times 10^8，所以每个圆至少有 \frac 14 的部分会在正方形里，于是限制为 \frac 14l\pi r^2\le 10^{16}(k-1)，解得 r\le \frac 2{\sqrt\pi}\cdot 10^8\cdot \sqrt{\frac{k-1}l}。因此比它大的都一定合法。

因此我们可以知道答案上界为后面这一坨东西。那这有什么用呢？考虑两个点对应圆相交等价于 \operatorname{dis}\le 2r，而对于一个点来说和它距离不超过 2r 的点数期望相当于把半径改成 2r 之后的面积之和再除以 10^{16}。而我们知道 r 的上界就使得期望的被覆盖次数为 k，因此翻倍之后被覆盖次数的期望也是 4k 左右。

这也就是说对于每个圆来说和它相交的点数都是 O(k) 的，因此我们只需要把它们都找到即可。于是到这里终于可以用上和上一题一样的方法了，按照 2r 划分平面，枚举周围 3\times 3 范围内的点。实际上这个范围的点数也可以用和刚才一样的方法分析出是 O(k) 的。

于是我们直接枚举每一个点作为 C 的圆心，实时维护一下目前已知的答案 r，每次先检查一下当前点能否更新答案。用平面最近点对类似的结论，在随机情况下答案期望的更新次数为 O(\log)（实际上本题因为本身点就是随机的所以直接顺序做就是对的）。于是如果答案可以被更新，就重新开始二分，每次减半的时候就重构一次网格。

于是 s=O(nk)，每次二分最多重构 \log \epsilon^{-1} 次，总复杂度 O(nk\log n+k\log n\log \epsilon^{-1})。

P9062

平面上有 n 个点，q 次查询区间最近点对。

不会具体细节。

考虑类似普通区间最近点对的做法。根据前面几个题应该已经不难注意到实际上在网格化的时候将边长设为当前答案的常数倍也是不会影响复杂度和正确性的，因此考虑以 2^0,2^1,\dots 分别作为边长。

之后对于 2^k 这一层的网格化，每加入一个新点的时候在周围 3\times 3 的网格内检查，把跟当前点距离小于 2^{k-1} 的点全都在这一层删除，能够证明正确性。然后对于所有在这 3\times 3 网格内的点全都作为类似支配对的点对集合，可以说明只有 O(n\log V) 个点对。

于是后面就直接对这 O(n\log V) 个支配对以及所有询问扫描线即可。由于常数原因，实际上这个 n\log V 偏大，因此可以写 O(1) 修改 O(\sqrt n) 查询的分块来平衡速度。总复杂度 O(n\log V+q\sqrt n)。