计算几何中的距离度量：欧氏、曼哈顿、切比雪夫与闵可夫斯基距离全解析（OI-wiki 实战篇）-迪斯科星球

计算几何中的距离度量：欧氏、曼哈顿、切比雪夫与闵可夫斯基距离全解析（OI-wiki 实战篇）

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读：本文以 OI-wiki 计算几何部分距离（distance）章节为骨架，系统讲解竞赛编程中最常用的四种距离度量——欧氏距离、曼哈顿距离、切比雪夫距离与闵可夫斯基距离的定义、公式、几何直觉与核心性质，并重点推导曼哈顿距离与切比雪夫距离之间的坐标变换关系。读完本文，你将掌握如何把"绝对值求和"的曼哈顿距离转化为"最大差值"的切比雪夫距离，从而把最值类问题化简为只统计坐标极值的 $O(n)$ 算法，并能在 OI / ICPC 赛题中直接复用文中的 C++ 与 Python 参考实现。

引言：为什么竞赛中要系统学习"距离"

在 OI / ICPC 的平面几何与网格类问题中，点与点之间的"距离"并不是唯一的度量方式。直线最短的欧氏距离适合几何直觉，但涉及绝对值运算的曼哈顿距离往往与网格行走、棋盘问题、货仓选址等场景绑定；切比雪夫距离则对应"八方向步数"等 max 型度量。不同度量在公式形态、计算代价与最值性质上差异巨大，选择不当会让问题复杂度陡增。

OI-wiki 将这一主题收录在 docs/geometry/distance.md，并在站点导航中与二维/三维计算几何基础并列（见 mkdocs.yml）。本文在继承该文档全部公式与例题的基础上，结合仓库的代码规范与测试机制（scripts/correctness_check.py），给出可直接复制运行的实现，并说明每种距离的适用场景与精度陷阱。

欧氏距离（Euclidean distance）

二维空间定义

欧氏距离，一般也称作欧几里得距离，是直觉上"两点间直线距离"的严格定义。在平面直角坐标系中，设点 $A,B$ 的坐标分别为 $A(x_1,y_1),B(x_2,y_2)$，则两点间的欧氏距离为：

$$ \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2} $$

例如，若 $A(6,5),B(2,2)$，代入公式：

$$ \left | AB \right | = \sqrt{\left ( 2 - 6 \right )^2 + \left ( 2 - 5 \right )^2} = \sqrt{4^2+3^2} = 5 $$

此外，点 $P(x,y)$ 到原点的欧氏距离可写作：

$$ |P| = \sqrt{x^2+y^2} $$

三维与 n 维推广：从勾股定理到求和公式

三维空间中，欧氏距离可以通过两次勾股定理分解得到。观察下图，在 $\triangle ADC$ 中 $\angle ADC = 90^\circ$，在 $\triangle ACB$ 中 $\angle ACB = 90^\circ$，因此：

$$ \begin{aligned} \therefore ~ |AB| &= \sqrt{|AC|^2+|BC|^2} \ &= \sqrt{|AD|^2+|CD|^2+|BC|^2} \end{aligned} $$

由此得到三维空间中欧氏距离的距离公式：

$$ \begin{gathered} \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2 + \left ( z_2 - z_1 \right )^2} \ |P| = \sqrt{x^2+y^2+z^2} \end{gathered} $$

以此类推，对于 $n$ 维空间中的两点 $\vec A(x_{11}, x_{12}, \cdots,x_{1n})$ 与 $\vec B(x_{21}, x_{22}, \cdots,x_{2n})$，欧氏距离为：

$$ \begin{aligned} \lVert\overrightarrow{AB}\rVert &= \sqrt{\left ( x_{11} - x_{21} \right )^2 + \left ( x_{12} - x_{22} \right )^2 + \cdot \cdot \cdot +\left ( x_{1n} - x_{2n} \right )^2}\ &= \sqrt{\sum_{i = 1}^{n}(x_{1i} - x_{2i})^2} \end{aligned} $$

欧氏距离的实用缺陷

欧氏距离虽然直观且应用广泛，但有一个明显的缺点：两个整点计算欧氏距离时，往往答案是浮点型，会存在一定误差。在需要精确比较距离大小、或需要整数答案的竞赛题目中，直接开根号容易引入浮点误差，此时应优先考虑避免开方的比较方式（如比较距离平方）或改用下文介绍的距离度量。NOIP2017 提高组"奶酪"一题正是利用三维欧氏距离判断两个球形空洞是否相交的经典应用，可作为该距离度量的入门例题。

曼哈顿距离（Manhattan distance）

定义与直观理解

在二维空间内，两个点之间的曼哈顿距离为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点 $A(x_1,y_1),B(x_2,y_2)$，则 $A,B$ 之间的曼哈顿距离为：

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

观察下图：在 $A,B$ 之间，黄线、橙线都表示曼哈顿距离，而红线、蓝线表示等价的曼哈顿距离（沿网格行走的不同路径），绿线表示欧氏距离：

曼哈顿距离的命名源于曼哈顿街区"只能沿街道行走"的直观——无论怎么绕行，从一点到另一点沿网格的路径总长度都等于横纵坐标差绝对值之和。例如 $A(25,20),B(10,10)$：

$$ d(A,B) = |20 - 10| + |25 - 10| = 10 + 15 = 25 $$

经过推导，$n$ 维空间的曼哈顿距离公式为：

$$ \begin{aligned} d(A,B) &= |x_1 - y_1| + |x_2 - y_2| + \cdot \cdot \cdot + |x_n - y_n|\ &= \sum_{i = 1}^{n}|x_i - y_i| \end{aligned} $$

数学性质

除公式外，曼哈顿距离满足度量空间的基本公理：

非负性：$d(i,j)\geq 0$，曼哈顿距离是一个非负数；
统一性（同一性）：一个点到自身的曼哈顿距离为 $0$，即 $d(i,i) = 0$；
对称性：$d(i,j) = d(j,i)$，即 $A$ 到 $B$ 与 $B$ 到 $A$ 的距离相等；
三角不等式：从点 $i$ 到 $j$ 的直接距离不会大于途经任何其它点 $k$ 的距离，即 $d(i,j)\leq d(i,k)+d(k,j)$。

这些性质保证了曼哈顿距离是一个合法的度量（metric），后续的坐标变换结论正是在此基础上建立的。

例题：P5098「USACO04OPEN」Cave Cows 3

题目要求 $\max\limits_{i,j} |x_1-x_2|+|y_1-y_2|$。直接枚举点对是 $O(n^2)$ 的，而利用绝对值展开可以做到 $O(n)$：假设 $x_1 - x_2 \geq 0$，根据 $y_1 - y_2$ 的符号分成两种情况：

当 $y_1 - y_2 \geq 0$ 时：$|x_1-x_2|+|y_1-y_2|=x_1 + y_1 - (x_2 + y_2)$；
当 $y_1 - y_2 < 0$ 时：$|x_1-x_2|+|y_1-y_2|=x_1 - y_1 - (x_2 - y_2)$。

因此只需要分别求出 $x+y$ 与 $x-y$ 的最大值和最小值，答案即为 $\max\big(\max(x+y)-\min(x+y),\ \max(x-y)-\min(x-y)\big)$。C++ 参考实现如下：

#include <algorithm> #include <cstdio> using namespace std; int main() { int n, x, y, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &x, &y); minx = min(minx, x + y), maxx = max(maxx, x + y); miny = min(miny, x - y), maxy = max(maxy, x - y); } printf("%d\n", max(maxx - minx, maxy - miny)); return 0; }

Python 实现：

minx = 0x7FFFFFFF maxx = 0 miny = 0x7FFFFFFF maxy = 0 n = int(input()) for i in range(1, n + 1): x, y = map(lambda x: int(x), input().split()) minx = min(minx, x + y) maxx = max(maxx, x + y) miny = min(miny, x - y) maxy = max(maxy, x - y) print(max(maxx - minx, maxy - miny))

注意：本题其实还有第二种做法——把曼哈顿距离转化为切比雪夫距离求解，这将在下文"相互转化"小节给出，两种思路最终写出的代码完全等价。

切比雪夫距离（Chebyshev distance）

切比雪夫距离是向量空间中的一种度量，两点之间的距离定义为其各坐标数值差的最大值。

在二维空间内，设点 $A(x_1,y_1),B(x_2,y_2)$，则 $A,B$ 之间的切比雪夫距离为：

$$ d(A,B) = \max(|x_1 - x_2|, |y_1 - y_2|) $$

$n$ 维空间中切比雪夫距离的公式为：

$$ \begin{aligned} d(x,y) &= \max\begin{Bmatrix} |x_1 - y_1|,|x_2 - y_2|,\cdot \cdot \cdot,|x_n - y_n|\end{Bmatrix} \ &= \max\begin{Bmatrix} |x_i - y_i|\end{Bmatrix}(i \in [1, n]) \end{aligned} $$

仍以 $A(25,20),B(10,10)$ 为例：

$$ d(A,B) = \max(|20 - 10|, |25 - 10|) = \max(10, 15) = 15 $$

从几何上看，切比雪夫距离对应棋盘上国王（king）一步可以走八个方向时，从一格到另一格所需的最少步数，因此也被称为"棋盘距离"。

曼哈顿距离与切比雪夫距离的相互转化

这是本节（也是整个 distance.md 文档）最核心的结论：曼哈顿距离与切比雪夫距离之间只差一个 $45^\circ$ 旋转与缩放变换。掌握这个变换，可以把很多"求和型"最值问题化为"取 max 型"问题，反之亦然。

过程：从两个正方形出发

首先画出平面直角坐标系上所有到原点的曼哈顿距离为 $1$ 的点，即满足方程 $|x| + |y| = 1$。将绝对值展开得到 4 个一次函数：

$$ \begin{aligned} &y = -x + 1 &(x \geq 0, y \geq 0) \ &y = x + 1 &(x \leq 0, y \geq 0) \ &y = x - 1 &(x \geq 0, y \leq 0) \ &y = -x - 1 &(x \leq 0, y \leq 0) \ \end{aligned} $$

将这 4 个函数画到平面直角坐标系上，得到一个边长为 $\sqrt{2}$ 的、斜置的正方形：

正方形边界上所有的点到原点的曼哈顿距离都是 $1$。

再考虑所有到原点的切比雪夫距离为 $1$ 的点，即满足 $\max(|x|,|y|)=1$。展开后同样得到 4 条线段：

$$ \begin{aligned} &y = 1&(-1\leq x \leq 1) \ &y = -1&(-1\leq x \leq 1) \ &x = 1,&(-1\leq y \leq 1) \ &x = -1,&(-1\leq y \leq 1) \ \end{aligned} $$

画到坐标系上，得到一个边长为 $2$ 的正方形：

正方形边界上所有的点到原点的切比雪夫距离都是 $1$。将两幅图对比可以发现：这两个正方形是相似图形（后者是前者旋转 $45^\circ$ 并放大的结果），这正是两类距离可互相转化的几何根源。

证明

假设 $A(x_1,y_1),B(x_2,y_2)$。把曼哈顿距离中的绝对值拆开，能够得到四个值，这四个值中的最大值是两个非负数之和，即曼哈顿距离。则 $A,B$ 两点的曼哈顿距离为：

$$ \begin{aligned} d(A,B)&=|x_1 - x_2| + |y_1 - y_2|\ &=\max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}\ &= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|) \end{aligned} $$

这恰是 $(x_1 + y_1,x_1 - y_1)$ 与 $(x_2 + y_2,x_2 - y_2)$ 两点之间的切比雪夫距离。于是得到第一条变换规则：

将每个点 $(x,y)$ 转化为 $(x + y, x - y)$，新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。

反过来，$A,B$ 两点的切比雪夫距离为：

$$ \begin{aligned} d(A,B)&=\max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}\ &=\max\begin{Bmatrix} \left|\dfrac{x_1 + y_1}{2}-\dfrac{x_2 + y_2}{2}\right|+\left|\dfrac{x_1 - y_1}{2}-\dfrac{x_2 - y_2}{2}\right|\end{Bmatrix} \end{aligned} $$

而这就是 $\left(\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}\right)$ 与 $\left(\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2}\right)$ 两点之间的曼哈顿距离。于是得到第二条变换规则：

将每个点 $(x,y)$ 转化为 $\left(\dfrac{x + y}{2},\dfrac{x - y}{2}\right)$，新坐标系下的曼哈顿距离即为原坐标系下的切比雪夫距离。

结论小结

曼哈顿坐标系是通过切比雪夫坐标系旋转 $45^\circ$ 后，再缩小到原来的一半得到的；
将点 $(x,y)$ 变为 $(x + y, x - y)$ 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离；
将点 $(x,y)$ 变为 $\left(\dfrac{x + y}{2},\dfrac{x - y}{2}\right)$ 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。

实战建议：碰到求切比雪夫距离或曼哈顿距离的题目时，往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，应灵活运用——例如需要统计"最远点对"时，切比雪夫距离的 $\max$ 形式配合坐标极值可以做到 $O(n)$；而需要统计"到某点距离之和"（货仓选址类）时，曼哈顿距离的线性形式配合排序与前缀和更容易处理。

用转化重解 P5098（第二种做法）

把题目所求的曼哈顿距离转化为切比雪夫距离：将每个点的坐标 $(x,y)$ 变为 $(x + y, x - y)$，所求答案变为：

$$ \max\limits_{i,j\in n}\begin{Bmatrix} \max\begin{Bmatrix} |x_i - x_j|,|y_i - y_j|\end{Bmatrix}\end{Bmatrix} $$

要使横坐标之差和纵坐标之差最大，只需预处理出变换后 $x,y$ 的最大值和最小值即可。C++ 实现：

#include <algorithm> #include <cstdio> using namespace std; int main() { int n, x, y, a, b, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &a, &b); x = a + b, y = a - b; minx = min(minx, x), maxx = max(maxx, x); miny = min(miny, y), maxy = max(maxy, y); } printf("%d\n", max(maxx - minx, maxy - miny)); return 0; }

Python 实现：

minx = 0x7FFFFFFF maxx = 0 miny = 0x7FFFFFFF maxy = 0 n = int(input()) for i in range(1, n + 1): a, b = map(lambda x: int(x), input().split()) x = a + b y = a - b minx = min(minx, x) maxx = max(maxx, x) miny = min(miny, y) maxy = max(maxy, y) print(max(maxx - minx, maxy - miny))

对比两份代码可以发现：两种不同的思路（直接展开绝对值 vs 先变换再取极值），写出来的代码完全等价。这也从侧面印证了坐标变换不改变问题本质，只是提供了更直观的建模视角。

闵可夫斯基距离：统一四种度量的框架

我们定义 $n$ 维空间中两点 $X(x_1, x_2, \dots, x_n)$ 与 $Y(y_1, y_2, \dots, y_n)$ 之间的闵可夫斯基距离（Minkowski distance）为：

$$ D(X, Y) = \left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right)^{\frac{1}{p}} $$

其中参数 $p$ 的不同取值对应不同的距离度量，特殊情形如下：

当 $p=1$ 时，$D(X, Y) = \sum_{i=1}^n \left\vert x_i - y_i \right\vert$，即为曼哈顿距离；
当 $p=2$ 时，$D(X, Y) = \left(\sum_{i=1}^n (x_i - y_i)^2\right)^{1/2}$，即为欧几里得距离；
当 $p \to \infty$ 时，$D(X, Y) = \lim_{p \to \infty}\left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right) ^{1/p} = \max\limits_{i=1}^n \left\vert x_i - y_i \right\vert$，即为切比雪夫距离。

注意：当 $p \ge 1$ 时，闵可夫斯基距离才是度量（满足三角不等式）；$p < 1$ 时不满足三角不等式，不再是严格意义上的距离。这也解释了为什么切比雪夫距离作为 $p\to\infty$ 的极限仍是一种合法度量。

至此，本文介绍的四类距离可以统一到同一参数族中：曼哈顿（$p=1$）、欧氏（$p=2$）、切比雪夫（$p\to\infty$），而曼哈顿与切比雪夫之间又存在 $45^\circ$ 旋转 + 缩放的坐标变换关系，形成了完整自洽的知识闭环。

实战要点与仓库使用建议

精度与溢出：欧氏距离涉及开方，整点答案通常为浮点型，存在精度误差；在需要精确比较时建议比较距离平方或采用整数运算。曼哈顿距离中 $x+y$ 与 $x-y$ 的极值统计直接使用int即可，但若坐标绝对值较大，注意中间值可能溢出，必要时使用long long。
复杂度收益：曼哈顿/切比雪夫距离的最远点对问题，通过坐标变换 + 维护极值可以做到 $O(n)$（如 P5098），远优于 $O(n^2)$ 枚举；"到某点距离和"类问题（如 P3964）则依赖排序与前缀和优化，相关技巧可与仓库中 docs/ds/prefix-sum.md 等章节配合学习。
验证与测试机制：OI-wiki 仓库对文档中的代码示例有一套自动化正确性校验流程：scripts/get_files_to_test.py 会根据变更文件自动关联code/目录下的主文件与examples/目录下的.in/.ans测试数据，再由 scripts/correctness_check.py 用g++ -std=c++17编译并对拍（diff -b -B忽略行尾空白与空行差异）。这意味着你看到的示例代码经过真实数据校验，可直接在本地用相同方式验证自己的实现。
进一步阅读：距离度量是计算几何的基础工具，后续可继续学习仓库中的平面最近点对（nearest-points）、旋转卡壳与凸包等章节，它们在很多题目中都与距离的最值问题深度耦合。

参考资料与链接

浅谈三种常见的距离算法（洛谷博客，感谢作者 xuxing 的授权）
切比雪夫距离 - 维基百科
Minkowski distance - Wikipedia（闵可夫斯基距离的度量性质证明）
OI-wiki 相关章节：docs/geometry/distance.md、二维计算几何基础、三维计算几何基础

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析