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

· · 个人记录

链接：参考博客

一直以为没有用，然后就几乎惨遭爆零了

区别于常见的欧式距离（就是小学、初中数学学的“距离”），曼哈顿距离和切比雪夫距离是OI中常考的“距离”。

曼哈顿距离：dis_{i, j} = |x_i - x_j| + |y_i - y_j|（一层套一层）

切比雪夫距离：dis_{i, j} = max(|x_i - x_j|, |y_i - y_j|)（一个环套一个环）

二者间的关系

图形上的关系：

与原点距离为1的点的分布范围：

曼哈顿距离的正方形逆时针旋转45度并且放大 \sqrt 2 倍 即为切比雪夫距离。

曼哈顿距离：（复制开头的博客的图片）

切比雪夫距离：

坐标数值上的关系：

计算曼哈顿距离所用坐标 (x, y) ---> (x + y, x - y) 即可变为计算切比雪夫距离所用坐标。即：之前的坐标的曼哈顿距离 = 之后的坐标的切比雪夫距离。

计算切比雪夫距离所用坐标 (x, y) ---> (\frac{x + y}{2}, \frac{x - y}{2}) 即可变为计算曼哈顿距离所用坐标。即：之前的坐标的切比雪夫距离 = 之后的坐标的曼哈顿距离。

简而言之：

曼哈顿------> 切比雪夫：(x, y) ---> (x + y, x - y)；

切比雪夫 -------> 曼哈顿： (x, y) ---> (\frac{x + y}{2}, \frac{x - y}{2})

应用：

有些题目选用曼哈顿距离更方便计算；而有些题目却更容易用切比雪夫距离实现。利用此公式可以做到二者之间的转化。

如果用某一种距离无法解题，或者有明显 45 度斜线的特征且用平直线似乎更方便的话，还是要尝试转换一下的。

例题：

P6143 [USACO20FEB]Equilateral Triangles P

题意：

求曼哈顿等边三角形数量。

题解：

通过手玩我们发现等边三角形可以套在一个矩形（平行于坐标轴）里面。并且一定有一条45度斜线。这样在切比雪夫距离中就一定有一条平直线段。又因为同一线段两种距离一定相等，因此转为切比雪夫距离以后第三个点所在的可行位置可以轻易得出：是一个线段。因此前缀和优化即可。

my record

P3964 [TJOI2013]松鼠聚会

题意：

给定 n 个点坐标，要求确定一个点，让所有点到该点的切比雪夫距离最小。输出最小值。

题解：

转为曼哈顿距离后可以拆分横纵坐标单独对待，分类讨论转化为前缀和问题。

my record