算法简介：外酥里嫩

众所周知，我们在数学上的两点间距离一般指的是直线距离。也就是欧几里得距离，但是，这篇文章我们要讲的是另外两个常用的距离，曼哈顿还有切比雪夫距离。

所谓曼哈顿距离，对于二维直角坐标系来说，他就是两个点的横坐标之差还有纵坐标之差的和。我们还会用他来计算出切比雪夫距离的计算方式，所以说开始吧~

算法演示：大火宽油

首先来看看曼哈顿距离，虽然说我们已经知道曼哈顿距离是什么，也知道怎么去求他，但是呢题目肯定不会考你模板的，所以说我们来一个经典例题试试水。

Clarke 是一位患有多重人格障碍的患者。有一天，他变成了一个几何学的学习者。他对一种有趣的距离一一曼哈顿距离进行了研究。
点 $A(x_A,y_A)$ 和点 $B(x_B,y_B)$ 之间的曼哈顿距离是 $|x_A - x_B| + |y_A - y_B|$ 。
现在他想要找到 $n$ 个点中任意两点之间的最大距离。

那么其实就是式子转化的问题，因为我们肯定不可以用 $n^2$ 复杂度过这道题，所以说我们要考虑一种类似线性的做法。这就要基于式子的变形了，我们发现这个绝对值非常的难受，所以说我们首先需要的就是去掉绝对值。

大力分讨一波，就是：

$x_A - x_B\ge 0,y_A - y_B\ge 0$ 然后化简为 $x_A - x_B + y_A - y_B$
$x_A - x_B\ge 0,y_A - y_B\le 0$ 然后化简为 $x_A - x_B + y_B - y_A$
$x_A - x_B\le 0,y_A - y_B\ge 0$ 然后化简为 $x_B - x_A + y_A - y_B$
$x_A - x_B\le 0,y_A - y_B\le 0$ 然后化简为 $x_B - x_A + y_B - y_A$

于是乎我们本能的想到了把相同的未知数凑到一起，上面的式子会分别变为：

$(x_A + y_A) - (x_B- y_B)$
$(x_A - y_A) - (x_B - y_B)$
$(- x_A + y_A)- (-x_B + y_B)$
$(- x_A - y_A) - (-x_B - y_B)$

于是就发现了大力枚举每一个点的每一维坐标的正负，找到他们的对应方案的最大值以及最小值。不过注意，我们优先枚举取号的情况，这是因为我们的式子是基于分讨情况而定的，如果一起搞的话就会出现混淆的情况。

算法模板：武火急烹

最后贴代码：

// p : 每个点的坐标
// n : 点的数量
// k : 坐标维度数量
// 显而易见这个算法是可以拓展至 k 维的
ll max_Manhattan(ll p[][10],int n,int k)
{
	ll ans=0;
	for (int s=0;s<(1<<k);++s)
	{
		ll mx=-1e18,mn=1e18;
		for (int i=0;i<n;++i)
		{
			ll tmp=0;
			for (int j=0;j<k;++j)
				tmp+=(s&(1<<j))?p[i][j]:-p[i][j];
			mx=max(mx,tmp),mn=min(mn,tmp);
		}
		ans=max(ans,mx-mn);
	}
	return ans;
}

算法进阶：文火慢煨

那么说完了曼哈顿距离，接下来就是切比雪夫了。所谓切比雪夫距离，是说对于两个点 $A(x_A,y_A)$ 与 $B(x_B, y_B)$ 他们的切比雪夫距离就是 $\operatorname{max}(|x_A-x_B|,|y_A-y_B|)$

一样的，这个 $\operatorname{max}$ 就很讨厌，问题就是这么把它消掉，显而易见这玩意过于奇怪，似乎无法找到一个直接证明的方式，我们不妨来一个猜想。首先画出平面直角坐标系中，距离远点的切比雪夫距离为 $1$ 的点的数量（左图）。

单独看可能没啥感觉，但是说如果我们把距离原点曼哈顿距离为一的点在图上描出来（右图）这时候就发现了一个神奇的地方，这两个图形……以原点为中心旋转相似！

但是如何证明呢？我们可以假设这个命题是正确的，如果一切能够说得通，那就说明旋转可以把坐标点在曼哈顿与切比雪夫之间转化。

首先来看这两幅图中左图切比雪夫距离为一的坐标点到右图曼哈顿距离的映射方式。既然我们已知的是曼哈顿距离，那么我们就可以用曼哈顿距离坐标系里的坐标来表示出切比雪夫坐标系里的坐标就可以了。

由于我们规定的是左图是曼哈顿距离原点距离为 $1$ 的点，也就是说代入了曼哈顿距离的式子应该是：$|x|+|y|=1$ 分类讨论了一下取值范围就是：

$x\ge 0,y\ge 0 \qquad x+y=1$
$x\ge 0,y\lt 0\qquad x-y=1$
$x\lt 0,y\ge 0 \qquad -(x-y)=1$
$x\lt 0,y\lt 0 \qquad -(x+y)=1$

曼哈顿距离就是这四个距离中的最大值，把他们综合了也就是 $|x+y|=|-(x+y)|,|x-y|=|-(x-y)|$ 之后，答案从 $\operatorname{max}\left\{x+y,x-y,-(x-y),-(x+y)\right\}$ 变成了形式：$\operatorname{max}\left\{|x+y|,|x-y|\right\}$ 。

这时候，神奇的一刻来临 —— 掏出我们的切比雪夫公式：$\operatorname{max}(|x_A-x_B|,|y_A-y_B|)$ ，由于说我们也是表示距原点切比雪夫距离为 $1$ 的点，也就是说 $(x_B,y_B)$ 就是原点 $(0,0)$ 代入方程式变成了 $\operatorname{max}\{|x_A|,|y_A|\}$

这时候，切比雪夫坐标系里的点，就可以用曼哈顿距离坐标系里的点搞定了 $x=x_A+y_A,y=x_A-y_B$ 用这个式子把切比雪夫距离转化为曼哈顿距离即可求解！

算法例题：锅巴凶猛

那么一样的，题目肯定不会让你傻傻做例题，那么最最经典的，当然还是切比雪夫距离最大点对，当然是二维（你怎么知道我不会高维）如果只是二维的话，就只需要在刚刚曼哈顿的基础上加上这个函数：

void CHtoMA() {
    for(int i = 1; i <= n; i++) {
        int px = a[i].x, py = a[i].y;
        a[i].x = px + py;
        a[i].y = px - py;
    }
}

当然如果有特殊需求需要把曼哈顿距离转化为切比雪夫，那就用小学和差问题解一解就可以：

void MAtoCH() {
    for(int i = 1; i <= n; i++) {
        int px = a[i].x, py = a[i].y;
        a[i].x = (px + py) / 2;
        a[i].y = (px - py) / 2;
    }
}