专栏文章

距离类问题(最全)

wwallace_QwQ
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4f18k
此快照首次捕获于
2025/12/01 20:23
3 个月前
此快照最后确认于
2025/12/01 20:23
3 个月前
查看原文

0.前言

这一类题目的做法极其死板和唯一，就是两种距离的相互转化，似乎主要的困难点就在于知道这个 trick。
但是这个 trick 本身也并不困难，极其容易学会，同时可以帮助你切掉不少水蓝，水紫。

1.基本定义

1.1 曼哈顿距离

对于二维平面上的两点 A(x1,y1)A(x_1, y_1) 和 B(x2,y2)B(x_2, y_2)，曼哈顿距离定义为：
dM(A,B)=∣x1−x2∣+∣y1−y2∣d_M(A, B) = |x_1 - x_2| + |y_1 - y_2|
实际应用：两点在四联通棋盘之间的距离。

性质：

由于曼哈顿距离的 xx 轴，yy 轴相互独立，所以考虑分开处理。
以下的性质自带一个对坐标进行排序的 O(nlog⁡n)O(n\log n) 复杂度和预处理的 O(n)O(n) 复杂度。
  1. 可以 O(1)O(1) 求出一个点到其他所有点的距离之和。
how
设我们当且这个点在排序后的数组排名为 kk。
那么 xx 轴上的答案即为 k×xk−∑i=1kxi+∑i=k+1nxi−(n−k)×xkk\times x_k-\sum_{i=1}^kx_i+\sum_{i=k+1}^nx_i-(n-k)\times x_k
yy 轴同理。
  1. 可以 O(n)O(n) 求出所有点两两之间的距离和。
how
设fxifx_i 表示排序后的前 ii 个点两两之间 xx 轴上的距离和。
fxi=fxi−1+(i−1)×(xi−xi−1)fx_i=fx_{i-1}+(i-1)\times(x_i-x_{i-1})
yy 轴同理。

1.2 切比雪夫距离

对于二维平面上的两点 A(x1,y1)A(x_1, y_1) 和 B(x2,y2)B(x_2, y_2)，切比雪夫距离定义为：
dC(A,B)=max⁡(∣x1−x2∣,∣y1−y2∣)d_C(A, B) = \max(|x_1 - x_2|, |y_1 - y_2|)
实际应用：两点在八联通棋盘之间的距离，也被称为棋盘距离。

性质：

  1. 可以 O(n)O(n) 求出所有点两两之间的距离最大值。
how
求出 xx 最大值，xx 最小值，yy 最大值，yy 最小值即可。
  1. 可以找出有多少指定点到某个点的距离 ≤d\le d 。
how
经典二维数点问题。
  1. 可以找出距离某个点第 kk 近的指定点与其的距离。
how
在性质 2 上套一个二分。

2.二维相互转换

2.1曼哈顿距离到切比雪夫距离的转换

通过坐标变换 (x,y)→(x+y,x−y)(x, y) \rightarrow (x + y, x - y)，可以将曼哈顿距离问题转化为切比雪夫距离问题。
dM(A,B)=∣x1−x2∣+∣y1−y2∣=max⁡{x1−x2+y1−y2,x2−x1+y1−y2,x1−x2+y2−y1,x2−x1+y2−y1}=max{∣(x1+y1)−(x2+y2)∣,∣(x1−y1)−(x2−y2)∣}\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)→(x+y2,x−y2)(x, y) \rightarrow \left(\frac{x+y}{2}, \frac{x-y}{2}\right)，可以将切比雪夫距离问题转化为曼哈顿距离问题。
注意
为了避免坐标除以 2 导致的精度误差，我们一般先不除以 2，而是求出答案后统一除以 2。

3.更高维转换

结论：xx 维的曼哈顿度量空间只能映射到 2x−12^{x-1} 维的切比雪夫度量空间。
即映射到的每一维是系数为 ±1\pm1 的线性组合，并去除对称的。
如三维的转化：
(x,y,z)→(x+y+z,−x+y+z,x−y+z,x+y−z)(x,y,z)\to(x+y+z,-x+y+z,x-y+z,x+y-z)

4.例题

T1.P3964 [TJOI2013] 松鼠聚会

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

T2.P8075 [COCI2009-2010#7] KRALJEVI

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

T3.AT_abc351_e [ABC351E] Jump Distance Sum

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

T4.P3439 [POI2006] MAG-Warehouse

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

T5.P5098 [USACO04OPEN] Cave Cows 3

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

T6.P4648 [IOI2007] pairs 动物对数

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

T7.AT_abc233_h Manhattan Christmas Tree

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

T8.AT_code_festival_2017_quala_d Four Coloring

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

T9.P2906 [USACO08OPEN] Cow Neighborhoods G

题意：将曼哈顿距离不超过 dd 的点连边，求连通块数量和最大连通块大小。
hint
曼哈顿距离转切比雪夫距离。
用并查集维护每个连通块。
先对 xx 轴排序，再使用 setset 维护 yy 轴，每次只与最近的合并。

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

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

5.更多例题

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

6.总结

通过观察，我们不难发现，如果问题与求和有关，使用曼哈顿距离，若问题与比较大小，最值有关，使用切比雪夫距离。
或许其本质上为 abs 和 max⁡/min⁡\max/\min 的相互转化。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...