曼哈顿距离（Manhattan Distance）

解释：只能横着或竖着走，坐标上两点的距离。

假设存在两点 和 ，则：

对于上方求曼哈顿距离的式子，有四种情况：

观察发现，上方四种情况中反复出现了两个值 和 。 发现对于四种情况，曼哈顿距离也就是：

例题应用 求到所有定点的最大曼哈顿距离最小：

• AtCoder ABC 178 E
• Codeforces 1689 D

切比雪夫距离（Chebyshev distance）

解释：各坐标数值差绝对值的最大值。

假设存在两点 和 ，则：

这时忽然发现，之前曼哈顿距离得出的结论：

与切比雪夫距离的形式非常相似！并且如果将 A，B 两个点的坐标换成 与 ，这两个点的切比雪夫距离刚好等于 与 的曼哈顿距离。

那么可以得到另一个结论：

曼哈顿距离转切比雪夫距离

转化为 新坐标系下的切比雪夫距离，即为原坐标系下曼哈顿距离。

由上边的结论反向推导一下，得到了：

切比雪夫距离转曼哈顿距离

转化为 新坐标系下的曼哈顿距离，即为原坐标系下切比雪夫距离。

上方的例题中，正是利用了这个原理： 将曼哈顿距离转为切比雪夫距离后， 的 ， 坐标就相互独立了。

1. 求出转化后最小和最大的 坐标和 坐标。
2. 对于每个点算一下他们距离最小和最大的 的距离，取个 就是最远的距离。

例题应用 对于将切比雪夫距离转曼哈顿距离的问题（求到所有定点的切比雪夫距离之和最小）：

• 洛谷 P3964

几何图示与代码实现

以上用式子推导了一下两个距离的转化关系，如果转化为图示，会发现：

曼哈顿距离如图是一个以当前点为中心的菱形，切比雪夫距离如上图是一个当前点为中心的正方形。所以它们之间的相互转化相当于将这个图形 旋转 然后适当放缩。

所以：

• 曼哈顿转切比雪夫 = ① 旋转 ② 乘以
• 切比雪夫转曼哈顿 = ① 反向旋转 ② 除以

对于 Python 之类的语言，直接用 rotate 函数之类的方式改变坐标确实比较方便；而对于 C++ 来说，利用之前推出的式子，就能达成类似的效果。

详细转化步骤图解

第一步：曼哈顿距离转切比雪夫距离

转化为

第二步：切比雪夫距离转曼哈顿距离

转化为