1. 曼哈顿距离

1.1. 定义

设平面中有两点，坐标分别为 $(x_1,y_1),(x_2,y_2)$ ，则它们的曼哈顿距离 $dis=|x_1-x_2|+|y_1-y_2|$ ，即两点横纵坐标差之和。

设平面中有两点，坐标分别为 $(x_1,y_1),(x_2,y_2)$ ，则它们的切比雪夫距离 $dis=\max(|x_1-x_2|,|y_1,y_2|)$ ，即两点横纵坐标差的最大值。

两者之间好像没关系，但其实它们之间可以相互转换。用曼哈顿距离表示，与原点距离为 $1$ 的点会构成一个边长为 $\sqrt{2}$ 的正方形。

用切比雪夫距离表示，与原点距离为 $1$ 的点会构成一个边长为 $2$ 的正方形。

因此我们可以得出结论：

将原直角坐标系中的点 $(x,y)$ 的坐标变为 $(x+y,x-y)$ 后，原坐标系中的曼哈顿距离就变为了切比雪夫距离。

将原直角坐标系中的点 $(x,y)$ 的坐标变为 $(\frac{x+y}{2},\frac{x-y}{2})$ 后，原坐标系中的切比雪夫距离就变为曼哈顿距离。

其实就是把正方形旋转 $45$ 度进行转化。

切比雪夫距离计算时要取 $\max$ ，计算一个点到其他点的距离和时间复杂度为 $O(n)$ 。

而曼哈顿距离只有求和和绝对值两种操作，绝对值的话分别按 $x$ 和 $y$ 排个序后做个前缀和就可以 $O(1)$ 求了。