在计算距离时，我们一般都是求两点之间的直线距离，实际上距离算法并不只这一种，还有其他的距离算法在OI中也同样很重要。不同的距离算法都有明显的优缺点。本文主要讲解 三种 常见的距离算法，分别是 欧氏距离，曼哈顿距离，切比雪夫距离 。
欧氏距离，是一个通常采用的距离定义，指在 m 维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
欧氏距离 是最易于理解的一种距离算法。在数学的平面直角坐标系中，设点 A,B 的坐标分别为 A(x_1,y_1),B(x_2,y_2)，求点 A,B 之间的距离，我们一般会使用如下公式：
实际上这就是平面（二维空间）中两点欧氏距离的距离公式，除此之外，P(x,y) 到原点的欧氏距离可以用公式表示为：
举个栗子，在下图中 A,B 的坐标分别为 A(6,5),B(2,2)。
通过公式，我们很容易得到 A,B 两点间的欧氏距离：
那么，三维空间 中两点的欧氏距离公式呢？
我们来观察下图。
我们很容易发现，在△ADC中，∠ADC = 90^\circ；在△ ACB中，∠ACB = 90∘
由此可得，三维空间 中欧氏距离的距离公式为：
例题：[Luogu]P3958
以此类推，我们就得到了 n 维空间 中欧氏距离的距离公式：
欧氏距离虽然很有用，但也有明显的缺点。两个整点计算其欧氏距离时，往往答案是浮点型，会存在一定误差。
曼哈顿距离 是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。
在 二维空间 内，两个点之间的曼哈顿距离为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点
观察下图：
在 A,B 间，
黄线，橙线都表示曼哈顿距离，而红线，蓝线表示等价的曼哈顿距离，绿线表示欧氏距离。
同样的栗子，在下图中 A,B 的坐标分别为 A(6,5),B(2,2) 。
通过公式，我们很容易得到 A,B 两点间的曼哈顿距离：
经过推导，我们得到 n 维空间 的曼哈顿距离公式为：
除了公式之外，曼哈顿距离还具有以下 数学性质：
非负性
曼哈顿距离是一个非负数。
d(i,j)≥ 0
统一性
点到自身的曼哈顿距离为 0。
d(i,i) = 0
对称性
A 到 B 与 B 到 A 的曼哈顿距离相等，且是对称函数。
d(i,j) = d(j,i)
三角不等式
从点 i 到 j 的直接距离不会大于途经的任何其它点 k 的距离。
d(i,j)≤ d(i,k)+d(k,j)
例题：[Luogu]P5098
解析：
根据题意，对于式子 |x_1-x_2 |+|y_1-y_2 |，我们可以假设 x_1-x_2≥0，根据 y_1-y_2 的符号分成两种情况：
(y_1-y_2≥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 的最大值和最小值即能得出答案。
Code
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1, len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
int n, x, y, minx = 0x7fffffff, maxx, miny = 0x7fffffff, maxy;
int main() {
read(n);
for (int i = 1; i <= n; i++) {
read(x), read(y);
minx = min(minx, x + y), maxx = max(maxx, x + y);
miny = min(miny, x - y), maxy = max(maxy, x - y);
}
write(max(maxx - minx, maxy - miny));
putchar('\n');
return 0;
}
其实还有第二种做法，那就是把 曼哈顿距离 转化为 切比雪夫距离 求解，后面会讲到。
切比雪夫距离 是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。
在 二维空间 内，两个点之间的切比雪夫距离为它们横坐标之差的绝对值与纵坐标之差的绝对值的最大值。设点 A(x_1,y_1),B(x_2,y_2)，则 A,B 之间的切比雪夫距离用公式可以表示为：
仍然是这个栗子，下图中 A,B 的坐标分别为 A(6,5),B(2,2)。
同理，n 维空间 中切比雪夫距离的距离公式：
切比雪夫距离 的一般模型：
在国际象棋棋盘上，国王与王后从一个格子走到另一个格子的最短距离都是切比雪夫距离。
若网格图上的一个点只能到周围 8 个点，且到这 8 个点的距离都相同，则该网格图上两点的距离也为切比雪夫距离。
首先，我们考虑画出平面直角坐标系上所有到原点的 曼哈顿距离 为 1 的点。
通过公式，我们很容易得到方程 \left | x\right| +\left | y\right| = 1。
将绝对值展开，得到 4 个 一次函数 ，分别是：
将这 4 个函数画到平面直角坐标系上，得到一个边长为 \sqrt{2} 的正方形，如下图所示：
正方形边界上所有的点到原点的 曼哈顿距离 都是 1 。
同理，我们再考虑画出平面直角坐标系上所有到原点的 切比雪夫距离 为 1 的点。
通过公式，我们知道 max(∣x∣,∣y∣)=1 。
我们将式子展开，也同样可以得到可以得到 4 条 线段，分别是：
画到平面直角坐标系上，可以得到一个边长为 2 的正方形，如下图所示：
正方形边界上所有的点到原点的 切比雪夫距离 都是 1 。
将这两幅图对比，我们会神奇地发现：
这 2 个正方形是 相似图形 。
所以，曼哈顿距离 与 切比雪夫距离 之间会不会有联系呢？
接下来我们简略证明一下：
假设 A(x_1,y_1),B(x_2,y_2)，
A,B 两点的 曼哈顿距离 为：
我们很容易发现，这就是
所以将每一个点 (x,y) 转化为 (x + y, x - y)，新坐标系下的 切比雪夫距离 即为原坐标系下的 曼哈顿距离。
同理，A,B 两点的 切比雪夫距离 为：
而这就是
所以将每一个点 (x,y) 转化为
结论：
将切比雪夫坐标系旋转 45∘，再缩小到原来的一半，即可得到曼哈顿坐标系。
将点 (x,y) 的坐标变为 (x + y, x - y)，
原坐标系中的 曼哈顿距离 = 新坐标系中的 切比雪夫距离
将点 (x,y) 的坐标变为
原坐标系中的 切比雪夫距离 = 新坐标系中的 曼哈顿距离
碰到求 切比雪夫距离 或 曼哈顿距离 的题目时，我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，应该灵活运用。
例题：
[Luogu]P4648（曼哈顿距离转切比雪夫距离）
[Luogu]P3964（切比雪夫距离转曼哈顿距离）
最后给出 [Luogu]P5098 的第二种解法：
我们考虑将题目所求的 曼哈顿距离 转化为 切比雪夫距离，即把每个点的坐标 (x,y) 变为 (x + y, x - y)。
所求的答案就变为
现要使得横坐标之差和纵坐标之差最大，只需要预处理出 x,y 的最大值和最小值即可。
Code
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1, len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
int n, x, y, a, b, minx = 0x7fffffff, maxx, miny = 0x7fffffff, maxy;
int main() {
read(n);
for (int i = 1; i <= n; i++) {
read(a), read(b);
x = a + b, y = a - b;
minx = min(minx, x), maxx = max(maxx, x);
miny = min(miny, y), maxy = max(maxy, y);
}
write(max(maxx - minx, maxy - miny));
putchar('\n');
return 0;
}
对比两份代码，我们又能够发现，两种不同的思路，写出来的代码却是完全等价的，是不是很神奇呢？当然，更高深的东西需要大家另行研究。
联系客服
