常用距离算法详解

在计算距离时，我们一般都是求两点之间的直线距离，实际上距离算法并不只这一种，还有其他的距离算法在 $\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

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