切比雪夫距离

曼哈顿距离

若有点$A(x_1,y_1)$和$B(x_2,y_2)$则$A,B$两点的曼哈顿距离为$|x_1-x_2|+|y_1-y_2|$。

若要求$n$个点两两之间的曼哈顿距离之和因为$x$的贡献和$y$的贡献是分开的所以我们可以分别处理。

将$n$个点的$x$和$y$分别排序用前缀和来求解。时间复杂度为$O(n\log n)$。

切比雪夫距离

曼哈顿距离可以理解为每次可以向上、下、左、右四个方向中的一个方向走一步从一点走到另一点的的最小步数。

则切比雪夫距离就是可以向八个方向中的一个方向走一步从一点走到另一点的的最小步数。

若有点$A(x_1,y_1)$和$B(x_2,y_2)$则$A,B$两点的切比雪夫距离为$\max (|x_1-x_2|,|y_1-y_2|)$。

若要求$n$个点两两之间的切比雪夫距离之和因为$x$的贡献和$y$的贡献不是独立的所以好像只能一个个枚举用$O(n^2)$的时间复杂度来求解。

难道真的没有更快的做法吗

优化

我们可以将原坐标系上的点逆时针旋转$45^{\circ }$则$A(x_1,y_1)$在旋转后的坐标为$(x_A,y_A)$

$x_A=x_1\cos 45^{\circ }-y_1\sin 45^{\circ }=\frac{\sqrt{2}}{2}(x_1-y_1)$

$y_A=x_1\sin 45^{\circ }+y_1\cos 45^{\circ }=\frac{\sqrt{2}}{2}(x_1+y_1)$

再将点到原点的距离放大到原来的$\sqrt{2}$倍得$x_A=x_1-y_1,y_A=x_1+y_1$

同理$B(x_2,y_2)$通过上述转换后的坐标为$B^{\prime }(x_B,y_B)$$x_B=x_2-y_2,y_B=x_2+y_2$

$A,B$的切比雪夫距离为$\max (|x_1-x_2|,|y_1-y_2|)$

$A^{\prime },B^{\prime }$的曼哈顿距离为$|x_A-x_B|+|y_A-y_B|=|(x_1-y_1)-(x_2-y_2)|+|(x_1+y_1)-(x_2+y_2)|$
$=|(x_1-x_2)-(y_1-y_2)|+|(x_1-x_2)+(y_1-y_2)|$

令$t_x=x_1-x_2,t_y=y_1-y_2$

$A,B$的切比雪夫距离为$\max (|t_x|,|t_y|)$$A^{\prime },B^{\prime }$的曼哈顿距离为$|t_x-t_y|+|t_x+t_y|$

• 若$t_x>0,t_y>0$$|t_x-t_y|+|t_x+t_y|$在$t_x>t_y$时为$2t_x$在$t_x<t_y$时为$2t_y$
• 若$t_x>0,t_y<0$$|t_x-t_y|+|t_x+t_y|$在$t_x>-t_y$时为$2t_x$在$t_x<-t_y$时为$-2t_y$
• 若$t_x<0,t_y>0$$|t_x-t_y|+|t_x+t_y|$在$-t_x>t_y$时为$-2t_x$在$-t_x<t_y$时为$2t_y$
• 若$t_x<0,t_y<0$$|t_x-t_y|+|t_x+t_y|$在$-t_x>-t_y$时为$-2t_x$在$-t_x<-t_y$时为$-2t_y$

经过分类讨论我们发现$A^{\prime },B^{\prime }$的曼哈顿距离为$A,B$的切比雪夫距离的两倍。由此可得在求$n$个点两两之间的切比雪夫距离之和时将每个点逆时针旋转$45^{\circ }$在放大到原来的$\sqrt{2}$倍求新的点的曼哈顿距离在除以2即为原来$n$个点的切比雪夫距离。

这样求$n$个点两两之间的切比雪夫距离时间复杂度为$O(n\log n)$。