常用距离算法详解

## 前言 在计算距离时，我们一般都是求两点之间的直线距离，实际上距离算法并不只这一种，还有其他的距离算法在 $\mathrm{OI}$ 中也同样很重要。不同的距离算法都有明显的优缺点。本文主要讲解 **三种** 常见的距离算法，分别是 **欧氏距离**，**曼哈顿距离**，**切比雪夫距离** 。 ## 一、欧氏距离（欧几里得度量） **欧氏距离** 是最易于理解的一种距离算法。在数学的平面直角坐标系中，设点 $A,B$ 的坐标分别为 $A(x_1,y_1),B(x_2,y_2)$，求点 $A,B$ 之间的距离，我们一般会使用如下公式： $$ \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2} $$ 实际上这就是平面**（二维空间）**中两点欧氏距离的距离公式，除此之外，$P(x,y)$ 到原点的欧氏距离可以用公式表示为： $$ \left | P \right | = \sqrt{x^2+y^2} $$ 举个例子，在下图中 $A,B$ 的坐标分别为 $A(6,5),B(2,2)$。  通过公式，我们很容易得到 $A,B$ 两点间的欧氏距离： $$ \left | AB \right | = \sqrt{\left ( 2 - 6 \right )^2 + \left ( 2 - 5 \right )^2} = \sqrt{4^2+3^2} = 5 $$ 那么，**三维空间** 中两点的欧氏距离公式呢？ 我们来观察下图。  我们很容易发现，在$\triangle ADC$中，$\angle ADC = 90^\circ$；在$\triangle ACB$中，$\angle ACB = 90^\circ$ 。  由此可得，**三维空间** 中欧氏距离的距离公式为： $$ \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} $$ $$ \left | P\right | = \sqrt{x^2+y^2+z^2} $$ 以此类推，我们就得到了 $n$ **维空间** 中欧氏距离的距离公式：  **欧氏距离** 的一般模型： 在一个坐标系上，求从一个点到另一个点的最短距离。 **欧氏距离** 的缺点： 两个整点计算其欧氏距离时，往往答案是浮点型，会存在精度误差。 **例题：** **[[Luogu]P3958](https://www.luogu.org/problemnew/show/P3958)** **Description** 共 $T$ 组数据。在一个三维坐标系上，有 $n$ 个球体，坐标分别为 $(x_i, y_i, z_i)$，半径为 $r$ 。现在从 $z$ 轴的 $0$ 位置出发，所经过的位置一定要有球体覆盖，求能否到达 $z$ 轴的 $h$ 位置。 $(1 \leq n \leq 10^3,1 \leq h,r \leq 10^9,T \leq 20$，坐标的绝对值不超过 $10^9)$ **Solution** 考虑用 **并查集** 维护球体形成的连通块。 如何判断两个球体是否连通？ 这就要用到三维空间中的欧式距离公式： $$ \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} $$ 若两个球体球心之间的欧式距离 $|AB| \leq 2r$，则说明这两个球体相交或者相切，可以把它们合并到同一个连通块中。 对于每个连通块，如果与底面和顶面都相连，就能够到达，反之则不行。时间复杂度为 $O(n^2)$ 。 由于求欧式距离时存在精度误差，我们可以将不等式两边开平方，得到 $$ \left | AB \right |^2 \leq 4r^2 $$ **Code** ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; 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 * 10 + (c ^ 48); x = f ? -x : x; } template <class T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } T y = 1; int len = 1; for (; y <= x / 10; y *= 10) ++len; for (; len; --len, x %= y, y /= 10) putchar(x / y + 48); } const int MAXN = 1e3; int t, n, h, r, x[MAXN + 5], y[MAXN + 5], z[MAXN + 5], d[MAXN + 5], u[MAXN + 5]; inline LL dist(int i, int j) {//三维空间内两点间欧式距离的平方 return (LL) (x[i] - x[j]) * (x[i] - x[j]) + (LL) (y[i] - y[j]) * (y[i] - y[j]) + (LL) (z[i] - z[j]) * (z[i] - z[j]); } struct ufSet { int fa[MAXN + 5]; ufSet(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; } int find(int x) { return x != fa[x] ? fa[x] = find(fa[x]) : x; } inline void merge(int x, int y) { fa[find(x)] = find(y); } }; int main() { for (read(t); t; --t) { read(n), read(h), read(r); for (int i = 1; i <= n; ++i) read(x[i]), read(y[i]), read(z[i]); ufSet s(n); memset(d, 0, sizeof (d)); memset(u, 0, sizeof (u)); for (int i = 1; i <= n; ++i) for (int j = 1; j < i; ++j) if (dist(i, j) <= (LL) 4 * r * r) //为避免精度误差，这里对不等式两边开平方 s.merge(i, j);//合并到同一个连通块中 bool flag = 0; for (int i = 1; i <= n; ++i) { if (z[i] - r <= 0) d[s.find(i)] = 1;//与底面相连 if (z[i] + r >= h) u[s.find(i)] = 1;//与顶面相连 if (d[s.find(i)] && u[s.find(i)]) {//如果一个连通块与底面和顶面都相连 flag = 1; break; } } puts(flag ? "Yes" : "No"); } return 0; } ``` ## 二、曼哈顿距离 在 **二维空间** 内，两个点之间的曼哈顿距离为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点 $A(x_1,y_1),B(x_2,y_2)$，则 $A,B$ 之间的曼哈顿距离用公式可以表示为： $$ d(A,B) = \left | x_1 - x_2\right | + \left | y_1 - y_2 \right | $$ 观察下图：  在 $A,B$ 间，$\color{yellow}{\text{黄线}}$，$\color{orange}{\text{橙线}}$ 都表示曼哈顿距离，而 $\color{red}{\text{红线}}$，$\color{blue}{\text{蓝线}}$ 表示 **等价** 的曼哈顿距离，$\color{green}{\text{绿线}}$ 表示欧氏距离。 同样的例子，在下图中 $A,B$ 的坐标分别为 $A(6,5),B(2,2)$ 。  通过公式，我们很容易得到 $A,B$ 两点间的曼哈顿距离： $$ d(A,B) = \left | 6 - 2\right | + \left | 5 - 2\right | = 4 + 3 = 7 $$ $n$ **维空间** 的曼哈顿距离公式：  除了公式之外，曼哈顿距离还具有以下 **数学性质**： **非负性** 曼哈顿距离是一个非负数。 $d(i,j)\geq 0$ **统一性** 点到自身的曼哈顿距离为 $0$。 $d(i,i) = 0$ **对称性** $A$ 到 $B$ 与 $B$ 到 $A$ 的曼哈顿距离相等，且是对称函数。 $d(i,j) = d(j,i)$ **三角不等式** 从点 $i$ 到 $j$ 的直接距离不会大于途经的任何其它点 $k$ 的距离。 $d(i,j)\leq d(i,k)+d(k,j)$ **曼哈顿距离** 的一般模型： 在国际象棋棋盘上，车从一个格子走到另一个格子的最短距离就是曼哈顿距离。 若网格图上的一个点只能到上下左右 $4$ 个点，且到这 $4$ 个点的距离都相同，则该网格图上两点的距离也为曼哈顿距离。 **例题：** **[[Luogu]P5098](https://www.luogu.org/problemnew/show/P5098)** **Description** 给定 $n$ 个点，每个点的坐标为 $(x,y)$，求曼哈顿距离的最大点对，输出这个最大值。 $(1 \leq n \leq 5 \times 10^4,-10^6 \leq x,y \leq 10^6)$ **Solution 1** 根据题意，对于式子 $\left | x_1-x_2\right| +\left | y_1-y_2\right| $，我们可以分成四种情况考虑： 第一种情况：$x_1 - x_2 \geq 0,y_1 - y_2 \geq 0$  第二种情况：$x_1 - x_2 < 0,y_1 - y_2 \geq 0$  第三种情况：$x_1 - x_2 \geq 0,y_1 - y_2 < 0$  第四种情况：$x_1 - x_2 < 0,y_1 - y_2 < 0$  每种情况的答案要么只与 $x+y$ 的值有关，要么只与 $x-y$ 的值有关，所以最后的答案为 $$ \max \begin{Bmatrix} \max \begin{Bmatrix} x_i + y_i \end{Bmatrix} - \min \begin{Bmatrix} x_i + y_i \end{Bmatrix},\max \begin{Bmatrix} x_i - y_i \end{Bmatrix} - \min \begin{Bmatrix} x_i - y_i \end{Bmatrix} \end{Bmatrix} $$ **Code 1** ```cpp #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 * 10 + (c ^ 48); x = f ? -x : x; } template <class T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } T y = 1; int 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$ 之间的切比雪夫距离用公式可以表示为： $$ d(A,B) = \max(\left | x_1 - x_2\right | , \left | y_1 - y_2\right | ) $$ 仍然是这个例子，下图中 $A,B$ 的坐标分别为 $A(6,5),B(2,2)$。  $$ d(A,B) = \max(\left | 6 - 2\right | , \left | 5 - 2\right | )=\max(4,3)=4 $$ $n$ **维空间** 的切比雪夫距离公式：  **切比雪夫距离** 的一般模型： 在国际象棋棋盘上，国王与王后从一个格子走到另一个格子的最短距离都是切比雪夫距离。 若网格图上的一个点只能到周围 $8$ 个点，且到这 $8$ 个点的距离都相同，则该网格图上两点的距离也为切比雪夫距离。 ## 四、二维曼哈顿距离与切比雪夫距离的相互转化 首先，我们考虑画出平面直角坐标系上所有到原点的 **曼哈顿距离** 为 $1$ 的点。 通过公式，我们很容易得到方程 $\left | x\right| +\left | y\right| = 1$。 将绝对值展开，得到 $4$ 个 **一次函数** ，分别是： $$ 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) $$ 将这 $4$ 个函数画到平面直角坐标系上，得到一个边长为 $\sqrt{2}$ 的正方形，如下图所示：  正方形边界上所有的点到原点的 **曼哈顿距离** 都是 $1$ 。 同理，我们再考虑画出平面直角坐标系上所有到原点的,**切比雪夫距离** 为 $1$ 的点。 通过公式，我们知道 $\max(\left |x\right | ,\left | y\right| )=1$。 我们将式子展开，也同样可以得到可以得到 $4$ 条 **线段**，分别是： $$ 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) $$ 画到平面直角坐标系上，可以得到一个边长为 $2$ 的正方形，如下图所示：  正方形边界上所有的点到原点的 **切比雪夫距离** 都是 $1$ 。 将这两幅图对比，我们会神奇地发现： 这 $2$ 个正方形是 **相似图形** 。 所以，**曼哈顿距离** 与 **切比雪夫距离** 之间会不会有联系呢？ 接下来我们简略证明一下： 假设 $A(x_1,y_1),B(x_2,y_2)$， $A,B$ 两点的 **曼哈顿距离** 为：  我们很容易发现，这就是 $(x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)$ 两点之间的 **切比雪夫距离**。 所以将每一个点 $(x,y)$ 转化为 $(x + y, x - y)$，新坐标系下的 **切比雪夫距离** 即为原坐标系下的 **曼哈顿距离**。 同理，$A,B$ 两点的 **切比雪夫距离** 为：  而这就是 $\left(\frac{x_1 + y_1}{2},\frac{x_1 - y_1}{2}\right),\left (\frac{x_2 + y_2}{2},\frac{x_2 - y_2}{2}\right)$ 两点之间的 **曼哈顿距离**。 所以将每一个点 $(x,y)$ 转化为 $\left(\frac{x + y}{2},\frac{x - y}{2}\right)$，新坐标系下的 **曼哈顿距离** 即为原坐标系下的 **切比雪夫距离**。 **结论：** 将切比雪夫坐标系旋转 $45^\circ$，再缩小到原来的一半，即可得到曼哈顿坐标系。 将点 $(x,y)$ 的坐标变为 $(x + y, x - y)$， 原坐标系中的 **曼哈顿距离** $=$ 新坐标系中的 **切比雪夫距离** 将点 $(x,y)$ 的坐标变为 $\left( \frac{x + y}{2},\frac{x - y}{2} \right)$， 原坐标系中的 **切比雪夫距离** $=$ 新坐标系中的 **曼哈顿距离** 碰到求 **切比雪夫距离** 或 **曼哈顿距离** 的题目时，我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，要学会做出正确的选择。 **例题：** **[[Luogu]P5098](https://www.luogu.org/problemnew/show/P5098)** **Solution 2** 我们考虑将题目所求的 **曼哈顿距离** 转化为 **切比雪夫距离**，即把每个点的坐标 $(x,y)$ 变为 $(x + y, x - y)$ 。 所求的答案就变为 $\max \begin{Bmatrix} \max\begin{Bmatrix} \left | x_i - x_j\right| ,\left | y_i - y_j\right| \end{Bmatrix} \end{Bmatrix}$ 。 在所有点中，横坐标之差的最大值和纵坐标之差的最大值都有可能成为答案，所以我们只需要预处理出 $x,y$ 的最大值和最小值即可。时间复杂度为 $O(n)$ 。 **Code 2** ```cpp #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 * 10 + (c ^ 48); x = f ? -x : x; } template <class T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } T y = 1; int 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; } ``` **[[Luogu]P3964](https://www.luogu.org/problemnew/show/P3964)** **Description** 给定 $n$ 个点，每个点的坐标为 $(x_i,y_i)$，且点 $(x,y)$ 到它周围 $8$ 个点 $(x-1,y)(x+1,y),(x,y-1),(x,y+1),(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)$ 的距离均为 $1$ 。现要找到一个点，使其它点到这个点的距离和最小，输出这个最小值。 $(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$ **Solution** 很容易看出这道题属于 **切比雪夫距离** 的一般模型。即对于两个点 $(x_1, y_1),(x_2,y_2)$，它们之间的距离为 $$ \max(\left | x_1 - x_2\right | , \left | y_1 - y_2\right | ) $$ 直接求 **切比雪夫距离** 似乎很困难？考虑把 **切比雪夫距离** 转化为 **曼哈顿距离**，即把每个点的坐标 $(x,y)$ 变为 $\left(\frac{x + y}{2}, \frac{x - y}{2} \right)$ 。 枚举所选的点 $i$，我们只需要计算其它点到它的曼哈顿距离和即可。 如果某个点 $j$ 的横坐标 $x_j \leq x_i$，则它的对总距离的贡献为 $x_i - x_j$，反之则为 $x_j - x_i$ 。 这样就可以分两种情况讨论了。 设前 $k$ 个点的横坐标都 $\leq x_i$，那么所有点横坐标的贡献和为  对于 $\sum\limits_{i = 1}^k x_i$ 和 $\sum\limits_{i = k + 1}^n x_i$，我们可以预处理出 $x$ 的前缀和后 $O(1)$ 求得。 怎么求 $k$ 呢？显然可以将横坐标排序后二分得到。 纵坐标 $y$ 的计算方法与上面一样。时间复杂度为 $O(n \log n)$ 。 **切比雪夫距离** 转成 **曼哈顿距离** 时要除以 $2$，为了避免出现小数，我们可以横坐标和纵坐标同时乘上 $2$，最后答案除以 $2$。 **Code** ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; 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 * 10 + (c ^ 48); x = f ? -x : x; } template <class T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } T y = 1; int len = 1; for (; y <= x / 10; y *= 10) ++len; for (; len; --len, x %= y, y /= 10) putchar(x / y + 48); } const int MAXN = 1e5; int n, x[MAXN + 5], y[MAXN + 5], p[MAXN + 5], q[MAXN + 5]; LL ans = 0x7fffffffffffffff, prex[MAXN + 5], prey[MAXN + 5]; int main() { read(n); for (int a, b, i = 1; i <= n; ++i) { read(a), read(b); x[i] = p[i] = a + b, y[i] = q[i] = a - b;//转曼哈顿距离，且乘上 2 } sort(p + 1, p + n + 1), sort(q + 1, q + n + 1);//排序 for (int a, b, i = 1; i <= n; ++i)//维护前缀和 prex[i] = prex[i - 1] + p[i], prey[i] = prey[i - 1] + q[i]; for (int posx, posy, i = 1; i <= n; ++i) { posx = lower_bound(p + 1, p + n + 1, x[i]) - p; posy = lower_bound(q + 1, q + n + 1, y[i]) - q; //二分找到 x[i] 和 y[i] 是所有点中第几个大的 LL sumx, sumy; sumx = (LL) posx * x[i] - prex[posx] + prex[n] - prex[posx] - (LL) (n - posx) * x[i];//计算横坐标贡献 sumy = (LL) posy * y[i] - prey[posy] + prey[n] - prey[posy] - (LL) (n - posy) * y[i];//计算纵坐标贡献 ans = min(ans, sumx + sumy); } write(ans / 2);//答案不要忘记除回去 putchar('\n'); return 0; } ``` **练习** **[[Luogu]AT3557](https://www.luogu.org/problemnew/show/AT3557)** **[[Luogu]P3439](https://www.luogu.org/problemnew/show/P3439)** **[[Luogu]P2906](https://www.luogu.org/problemnew/show/P2906)** **[[Luogu]P4648](https://www.luogu.org/problemnew/show/P4648)**