距离

欧式距离（欧几里得距离）

平面直角坐标系中，设点 \(A,B\) 的坐标分别为 \(A(x_1,y_1),B(x_2,y_2)\) ，则两点的欧几里得距离为 \[ |\overrightarrow{AB}| = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \] 设点 \(P(x,y)\) ，则其到原点 \(O\) 的距离为 \[ |\overrightarrow{OP}| = \sqrt{x^2 + y^2} \]

推广至 \(n\) 维空间中，对于 \(A(a_1,a_2,\cdots,a_n),B(b_1,b_2,\cdots,b_n)\) ，有 \[ \|\overrightarrow{AB}\| = \sqrt{\sum_{i=1}^{n}(a_i-b_i)^2} = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2} \] 点 \(P(x_1,x_2,\cdots,x_n)\) 到原点 \(O\) 的距离为 \[ \|\overrightarrow{OP}\| = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2} \] 可以通过下图理解三维空间中的欧式距离为什么是 \(\sqrt{d}\) 而不是 \(\sqrt[3]{d}\)

一般情况下，欧式距离的计算结果为浮点数

因此在计算几何的题目中，一般先记录欧式距离的平方，最后再开根号

曼哈顿距离

在平面直角坐标系中，点 \(A(x_1,y_1),B(x_2,y_2)\) 间的 Manhattan 距离定义为 \[ d(A,B) = |x_1 - x_2| + |y_1 - y_2| \] 推广至 \(n\) 维空间中，设点 \(A(a_1,a_2,\cdots,a_n),B(b_1,b_2,\cdots,b_n)\) ，则有 \[ d(A,B) = \sum_{i=1}^{n}|a_i-b_i| = |a_1-b_1| + |a_2-b_2| + \cdots + |a_n-b_n| \] 不同于欧式距离，Manhattan 距离相同时不能确定唯一的路径，如下图

其中绿线表示欧式距离，不难发现它是唯一的，而其他颜色的线以及虚线均为合法路径

曼哈顿距离具有很有有趣的性质

非负性：曼哈顿距离为非负数
统一性：点到自身的距离为 \(0\)
对称性：\(A\) 到 \(B\) 与 \(B\) 到 \(A\) 的曼哈顿距离相等，且是对称函数（即 \(d(i,j) = d(j,i)\) ）
三角不等式：

这是最重要的性质。

点 \(i\) 到 \(j\) 的直接距离不会大于 \(i\) 到 \(k\) 的距离加 \(k\) 到 \(j\) 的距离。 \[ d(i,j) \le d(i,k) + d(k,j) \] 当且仅当 \(k\) 存在于 \(i,j\) 的合法最短路径上时，等式取等号。

对于一些题目，可以把绝对值拆开来分类讨论。

例如：CF491B New York Hotel

求距离每个餐厅最远的人的距离的最大值，说白了就是 \(d_{\max}(A,B)\) ，\(A,B\) 分别表示餐厅和人的集合。

观察公式 \(|x_i-x_j|+|y_i-y_j|\) 可以发现，一共有 \(4\) 种情况 \[ (x_i-x_j)-(y_i-y_j)\\ (x_j-x_i)-(y_i-y_j)\\ (x_i-x_j)-(y_j-y_i)\\ (x_j-x_i)-(y_j-y_i) \] 这么看好像有点花，我们用 \(a,b,c,d\) 来替代 \(x_i,y_i,x_j,y_j\) \[ \begin{aligned} (a-c)-(b-d) &\Rightarrow (a-b)-(c-d)\\ (c-a)-(b-d) &\Rightarrow (-a-b)-(-c-d)\\ (a-c)-(d-b) &\Rightarrow (a+b)-(c+d)\\ (c-a)-(d-b) &\Rightarrow (-a+b)-(-c+d) \end{aligned} \] 而在枚举每个餐厅的时候，其实就相当于固定了 \(c,d\) 。

于是我们只要统计每个人的 \(a-b,-a-b,a+b,-a+b\) 各自的最大值，这样减掉后面的 \(c,d\) 就是极大值了。

我们用类似的思路可以解决 P5098 [USACO04OPEN]Cave Cows 3 这道题

这道题求的是已知点集，两点的 Manhattan 距离最大值。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4+15))

int n,ans,s1,s2,s3,s4,x[N],y[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> x[i] >> y[i];
        up(s1, x[i] + y[i]); up(s2, x[i] - y[i]);
        up(s3, -x[i] + y[i]); up(s4, -x[i] - y[i]);
    }
    for(int i=1; i<=n; i++)
    {
        up(ans, max(s1 - (x[i] + y[i]), s2 - (x[i] - y[i])));
        up(ans, max(s3 - (-x[i] + y[i]), s4 - (-x[i] - y[i])));
    }
    cout << ans << '\n';
    return 0;
}

切比雪夫距离

咕咕咕... 目前没用到过

\(L_m\) 距离

~~鬼知道这玩意有啥用~~

一般地，我们定义平面上两点 \(A\left(x_1, y_1\right), B\left(x_2, y_2\right)\) 之间的 \(L_m\) 距离为 \[ d\left(L_m\right)=\left(\left|x_1-x_2\right|^m+\left|y_1-y_2\right|^m\right)^{\frac{1}{m}} \] 特殊的， \(L_1\) 距离就是曼哈顿距离， \(L_2\) 距离就是欧几里得距离。

~~这下好了，距离「大一统」了~~