距离

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

平面直角坐标系中，设点 $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;
}