距离

欧氏距离

欧氏距离,一般也称作欧几里得距离。在平面直角坐标系中,设点 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) ,通过公式,我们很容易得到 A,B 两点间的欧氏距离:

\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}

那么,三维空间中两点的欧氏距离公式呢?我们来观察下图。

dis-3-dimensional

我们很容易发现,在 \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}

NOIP2017 提高组 奶酪 就运用了这一知识,可以作为欧氏距离的例题。

以此类推,我们就得到了 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}

欧氏距离虽然很有用,但也有明显的缺点。两个整点计算其欧氏距离时,往往答案是浮点型,会存在一定误差。

曼哈顿距离

在二维空间内,两个点之间的曼哈顿距离(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|

观察下图:

manhattan-dis-diff

A,B 间,黄线、橙线都表示曼哈顿距离,而红线、蓝线表示等价的曼哈顿距离,绿线表示欧氏距离。

同样的例子,在下图中 A,B 的坐标分别为 A(25,20),B(10,10)

manhattan-dis

通过公式,我们很容易得到 A,B 两点间的曼哈顿距离:

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

  • 对称性

    A B B A 的曼哈顿距离相等,且是对称函数。

    d(i,j) = d(j,i)

  • 三角不等式

    从点 i j 的直接距离不会大于途经的任何其它点 k 的距离。

    d(i,j)\leq d(i,k)+d(k,j)

例题

P5098「USACO04OPEN」Cave Cows 3

根据题意,对于式子 |x_1-x_2|+|y_1-y_2| ,我们可以假设 x_1 - x_2 \geq 0 ,根据 y_1 - y_2 的符号分成两种情况:

  • (y_1 - y_2 \geq 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 + y_1 - (x_2 + y_2)

  • (y_1 - y_2 < 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 - y_1 - (x_2 - y_2)

只要分别求出 x+y, x-y 的最大值和最小值即能得出答案。

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <bits/stdc++.h>
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;
}

其实还有第二种做法,那就是把曼哈顿距离转化为切比雪夫距离求解,最后部分会讲到。

切比雪夫距离

切比雪夫距离(Chebyshev distance)是向量空间中的一种度量,二个点之间的距离定义为其各坐标数值差的最大值。1

在二维空间内,两个点之间的切比雪夫距离为它们横坐标之差的绝对值与纵坐标之差的绝对值的最大值。设点 A(x_1,y_1),B(x_2,y_2) ,则 A,B 之间的切比雪夫距离用公式可以表示为:

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

仍然是这个例子,下图中 A,B 的坐标分别为 A(25,20),B(10,10)

Chebyshev-dis

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

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}

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

首先,我们考虑画出平面直角坐标系上所有到原点的曼哈顿距离为 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 个函数画到平面直角坐标系上,得到一个边长为