平面内有 \(n\) 个点 \((x_i,y_i)\),两点间距离定义为曼哈顿距离,即 \(|x_1-x_2|+|y_1-y_2|\) 。
求所有点对中,距离最大值为多少。
原范围:\(n\le 50000\)。
提示1:绝对值不好整,想想办法
提示2:也可以使用经典套路:曼哈顿转切比雪夫
Solution 1
因为 \(|x_1-x_2|+|y_1-y_2|\) 中的绝对值不好办,所以对它对分类讨论。
不妨令 \(x_1<x_2\),则
-
\(y_1<y_2\) ,则 \(dis=(x_2+y_2)-(x_1+y_1)\)。
-
\(y_1>y_2\) ,则 \(dis=(x_2-y_2)-(x_1-y_1)\)。
所以,我们只需要求 \(x_i+y_i\) 和 \(x_i-y_i\) 的 \(max/min\) 即可,最终答案为
\[max\{max\{x_i+y_i\}-min\{x_i+y_i\}~~,~~max\{x_i-y_i\}-min\{x_i-y_i\}\} \]时间复杂度 \(O(n)\)。
Solution 2
原定的点 \((x,y)\rightarrow(x+y,x-y)\) 后,原曼哈顿距离就等于之后的切比雪夫距离。
即从 \(|x_1-x_2|+|y_1-y_2|\) 变成了 \(max\{|(x_1+y_1)-(x_2+y_2)|~~,~~|(x_1-y_1)+(x_2-y_2)|\}\)。
这个式子显然等价于Solution 1
中的式子,时间复杂度 \(O(n)\) 即可计算。