距离类问题(最全)

· · 算法·理论

0.前言

这一类题目的做法极其死板和唯一，就是两种距离的相互转化，似乎主要的困难点就在于知道这个 trick。

但是这个 trick 本身也并不困难，极其容易学会，同时可以帮助你切掉不少水蓝，水紫。

1.基本定义

1.1 曼哈顿距离

对于二维平面上的两点 A(x_1, y_1) 和 B(x_2, y_2)，曼哈顿距离定义为：

d_M(A, B) = |x_1 - x_2| + |y_1 - y_2|

实际应用：两点在四联通棋盘之间的距离。

性质：

由于曼哈顿距离的 x 轴，y 轴相互独立，所以考虑分开处理。

以下的性质自带一个对坐标进行排序的 O(n\log n) 复杂度和预处理的 O(n) 复杂度。

  1. 可以 O(1) 求出一个点到其他所有点的距离之和。 :::info[how] 设我们当且这个点在排序后的数组排名为 k。

那么 x 轴上的答案即为 k\times x_k-\sum_{i=1}^kx_i+\sum_{i=k+1}^nx_i-(n-k)\times x_k

::: 2. 可以 $O(n)$ 求出所有点两两之间的距离和。 :::info[how] 设$fx_i$ 表示排序后的前 $i$ 个点两两之间 $x$ 轴上的距离和。 $fx_i=fx_{i-1}+(i-1)\times(x_i-x_{i-1}) ::: ### 1.2 切比雪夫距离 对于二维平面上的两点 $A(x_1, y_1)$ 和 $B(x_2, y_2)$，切比雪夫距离定义为： $$d_C(A, B) = \max(|x_1 - x_2|, |y_1 - y_2|)$$ 实际应用：两点在八联通棋盘之间的距离，也被称为**棋盘距离**。 #### 性质： 1. 可以 $O(n)$ 求出所有点两两之间的距离最大值。 :::info[how] 求出 $x$ 最大值，$x$ 最小值，$y$ 最大值，$y$ 最小值即可。 ::: 2. 可以找出有多少指定点到某个点的距离 $\le d$ 。 :::info[how] 经典二维数点问题。 ::: 3. 可以找出距离某个点第 $k$ 近的指定点与其的距离。 :::info[how] 在性质 2 上套一个二分。 ::: ## 2.二维相互转换 ### 2.1曼哈顿距离到切比雪夫距离的转换 通过坐标变换 $(x, y) \rightarrow (x + y, x - y)$，可以将曼哈顿距离问题转化为切比雪夫距离问题。 $$ \begin{aligned} d_M(A,B)&=|x_1 - x_2|+|y_1 - y_2|\\ &=\max\{x_1-x_2+y_1-y_2,x_2-x_1+y_1-y_2,x_1-x_2+y_2-y_1,x_2-x_1+y_2-y_1\}\\ &=max\{|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|\} \end{aligned} $$ **几何解释**：这一变换相当于将坐标轴旋转45度并进行缩放，原坐标系中的菱形（曼哈顿距离等距线）变成了新坐标系中的正方形（切比雪夫距离等距线）。 ### 2.2切比雪夫距离到曼哈顿距离的转换 通过逆向变换 $(x, y) \rightarrow \left(\frac{x+y}{2}, \frac{x-y}{2}\right)$，可以将切比雪夫距离问题转化为曼哈顿距离问题。 :::info[注意] 为了避免坐标除以 2 导致的精度误差，我们一般先不除以 2，而是求出答案后统一除以 2。 ::: ## 3.更高维转换 结论：$x$ 维的曼哈顿度量空间只能映射到 $2^{x-1}$ 维的切比雪夫度量空间。 即映射到的每一维是系数为 $\pm1$ 的线性组合，并去除对称的。 如三维的转化： $(x,y,z)\to(x+y+z,-x+y+z,x-y+z,x+y-z)

4.例题

T1.P3964 [TJOI2013] 松鼠聚会

题意：找到一给定点，使得所有给定点到该点的切比雪夫距离之和最小。 :::info[hint] 切比雪夫距离转曼哈顿距离，然后使用性质 1。 :::

T2.P8075 [COCI2009-2010#7] KRALJEVI

题意：求出给定点两两之间的切比雪夫距离和。 :::info[hint] 切比雪夫距离转曼哈顿距离，然后使用性质 2。 :::

T3.AT_abc351_e [ABC351E] Jump Distance Sum

题意：给定点分成两份，求出每一份的给定点两两之间的切比雪夫距离和。 :::info[hint] 切比雪夫距离转曼哈顿距离，然后使用性质 2。 :::

T4.P3439 [POI2006] MAG-Warehouse

题意：找到平面上任意一点，使得所有给定点到该点的切比雪夫距离之和最小。 :::info[hint] 切比雪夫距离转曼哈顿距离，然后显然的 x 轴，y 轴分别取中位数。 :::

T5.P5098 [USACO04OPEN] Cave Cows 3

题意：求出所有给定点两两之间的曼哈顿距离最大值。 :::info[hint] 曼哈顿距离转切比雪夫距离，然后使用性质 1。 :::

T6.P4648 [IOI2007] pairs 动物对数

题意：求出一，二，三维空间有多少点对的曼哈顿距离小于 d。 :::info[hint] 高维曼哈顿距离转切比雪夫距离，然后使用性质 2。 :::

T7.AT_abc233_h Manhattan Christmas Tree

题意：多次查询，每次给出平面上的任意一点，求与该点的曼哈顿距离第k小的给定点的距离为多少。 :::info[hint] 曼哈顿距离转切比雪夫距离，然后使用性质 3，可以使用主席树维护。 :::

T8.AT_code_festival_2017_quala_d Four Coloring

题意：用四种颜色染色网格，使得曼哈顿距离为 d 的点颜色不同。 :::info[hint] 曼哈顿距离转切比雪夫距离，等距线变成矩形，就方便构造了。 :::

T9.P2906 [USACO08OPEN] Cow Neighborhoods G

题意：将曼哈顿距离不超过 d 的点连边，求连通块数量和最大连通块大小。 :::info[hint] 曼哈顿距离转切比雪夫距离。

用并查集维护每个连通块。

先对 x 轴排序，再使用 set 维护 y 轴，每次只与最近的合并。 :::

T10.[P5193 [TJOI2012] 炸弹](https://www.luogu.com.cn/problem/P5193

题意：将曼哈顿距离不超过 d 的点连边，求连通块数量。 :::info[hint] 同上。 :::

5.更多例题

  1. P4876 [USACO14MAR] The Lazy Cow G
  2. P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2)

    6.总结

    通过观察，我们不难发现，如果问题与求和有关，使用曼哈顿距离，若问题与比较大小，最值有关，使用切比雪夫距离。

或许其本质上为 abs 和 \max/\min 的相互转化。