曼哈顿距离

定义

设平面空间内存在两点，它们的坐标为 (x1,y1),(x2,y2)(x_1, y_1) , (x_2, y_2)，则两点之间的曼哈顿距离为 dis=∣x1−x2∣+∣y1−y2∣dis = |x_1 - x_2| + |y_1 - y_2|。

实际应用：两点在四联通棋盘之间的距离。

比如，(1,2),(−2,4)(1, 2), (-2, 4) 之间的距离是 55。

切比雪夫距离

定义

设平面空间内存在两点，它们的坐标为 (x1,y1),(x2,y2)(x_1, y_1) , (x_2, y_2)，则两点之间的切比雪夫距离为 dis=max⁡(∣x1−x2∣,∣y1−y2∣)dis = \max(|x_1 - x_2|, |y_1 - y_2|)。

实际应用：两点在八联通棋盘之间的距离。

比如，(1,2),(−2,4)(1, 2), (-2, 4) 之间的距离是 33。

曼哈顿转切比雪夫

将一个点 (x,y)(x, y) 的坐标变为 (x+y,x−y)(x + y, x - y) 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。

证明

考虑把绝对值改为分类讨论，于是可以得出

∣x1−x2∣+∣y1−y2∣=max⁡(x1−x2+y1−y2,x1−x2+y2−y1,x2−x1+y1−y2,x2−x1+y2−y1)=max⁡((x1+y1)−(x2−y2),(x1−y1)−(x2−y2),(x2−y2)−(x1+y1),(x2+y2)−(x1+y1))\begin{aligned} |x_1 - x_2| + |y_1 - y_2| &= \max(x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1, x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1)\\ &= \max((x_1 + y_1) - (x_2 - y_2), (x_1 - y_1) - (x_2 - y_2), (x_2 - y_2) - (x_1 + y_1), (x_2 + y_2) - (x_1 + y_1))\\ \end{aligned}

max⁡(∣x1′−x2′∣,∣y1′−y2′∣)=max⁡(x1′−x2′,x2′−x1′,y1′−y2′,y2′−y1′)\max(|x_1' - x_2'|, |y_1' - y_2'|) = \max(x_1' - x_2', x_2' - x_1', y_1' - y_2', y_2' - y_1')

其中 x,yx, y 表示原坐标系的坐标，而 x′,y′x', y' 表示新坐标系的坐标。

观察上式，显然可以发现 x′=x+y,y′=x−yx' = x + y, y' = x - y 可以使上面两个相等。

例题

首先考虑求出第 kk 近的点对距离。然后这个东西我们可以考虑二分答案 disdis，然后求出距离 ≤dis\le dis 的点对个数。

然后发现这个东西不好求，形状比较奇怪。考虑曼哈顿距离转切比雪夫距离，然后与一个点距离合法的点都在一个矩形里，然后这个东西可以二维数点，具体来讲，用一个 queue 维护 xx 维，再用 set 维护 yy 维。

时间复杂度为 O(nlog⁡2n)O(n \log^2 n)。

切比雪夫转曼哈顿

将一个点 (x,y)(x, y) 的坐标变为 (x+y2,x−y2)(\frac{x + y}2, \frac{x - y}2) 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。

证明

沿用上面的定义与结论 x′=x+y,y′=x−yx' = x + y, y' = x - y 可以得出：

x′+y′=x+y+x−y=2xx' + y' = x + y + x - y = 2x

x′−y′=x+y−x+y=2yx' - y' = x + y - x + y = 2y

所以结论得证。

例题

我们发现，因为 max⁡\max 的存在，一个点到其他点的切比雪夫距离和不好快速求，只能做到 O(n)O(n)。

考虑切比雪夫距离转曼哈顿距离。一个点 pp 到其他点的曼哈顿距离为 ∑i=1n∣xi−xp∣+∣yi−yp∣\sum_{i = 1}^n |x_i - x_p| + |y_i - y_p|，然后 x,yx, y 两维可以独立开来，这样问题就变成快速对每个 pp 求出 ∑i=1n∣ai−ap∣\sum_{i = 1}^n |a_i - a_p| 的值。显然排序之后可以前缀和 O(1)O(1) 求出任意一个 pp 的值，所以原问题也可以在 O(nlog⁡n)O(n \log n) 的时间复杂度里解决，瓶颈在排序。