给你一个下标从 0 开始的数组 points
,它表示二维平面上一些点的整数坐标,其中 points[i] = [xi, yi]
。
两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点,返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1:
**输入:** points = [[3,10],[5,15],[10,2],[4,4]]**输出:** 12**解释:** 移除每个点后的最大距离如下所示:- 移除第 0 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间,为 |5 - 10| + |15 - 2| = 18 。- 移除第 1 个点后,最大距离在点 (3, 10) 和 (10, 2) 之间,为 |3 - 10| + |10 - 2| = 15 。- 移除第 2 个点后,最大距离在点 (5, 15) 和 (4, 4) 之间,为 |5 - 4| + |15 - 4| = 12 。- 移除第 3 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间的,为 |5 - 10| + |15 - 2| = 18 。在恰好移除一个点后,任意两点之间的最大距离可能的最小值是 12 。
示例 2:
**输入:** points = [[1,1],[1,1],[1,1]]**输出:** 0**解释:** 移除任一点后,任意两点之间的最大距离都是 0 。
提示:
3 <= points.length <= 105
points[i].length == 2
1 <= points[i][0], points[i][1] <= 108
最小化曼哈顿距离
题目
给你一个下标从 0 开始的数组 points
,它表示二维平面上一些点的整数坐标,其中 points[i] = [xi, yi]
。
两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点,返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1:
**输入:** points = [[3,10],[5,15],[10,2],[4,4]]
**输出:** 12
**解释:** 移除每个点后的最大距离如下所示:
- 移除第 0 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间,为 |5 - 10| + |15 - 2| = 18 。
- 移除第 1 个点后,最大距离在点 (3, 10) 和 (10, 2) 之间,为 |3 - 10| + |10 - 2| = 15 。
- 移除第 2 个点后,最大距离在点 (5, 15) 和 (4, 4) 之间,为 |5 - 4| + |15 - 4| = 12 。
- 移除第 3 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间的,为 |5 - 10| + |15 - 2| = 18 。
在恰好移除一个点后,任意两点之间的最大距离可能的最小值是 12 。
示例 2:
**输入:** points = [[1,1],[1,1],[1,1]]
**输出:** 0
**解释:** 移除任一点后,任意两点之间的最大距离都是 0 。
提示:
3 <= points.length <= 105
points[i].length == 2
1 <= points[i][0], points[i][1] <= 108
题解
方法一:
思路
对于点(x_1,y_1)到(x_2,y_2)的曼哈顿距离$|x_1-x_2|+|y_1-y_2| \Rightarrow max(x_1-x_2+y_1-y_2, x_2-x_1+y_1-y_2, x_1-x_2+y_2-y_1, x_2-x_1-y_2-y_1)$
令$X_i=x_i-y_i, Y_i=x_i+y_i$, 得到$max(Y_1-Y_2, X_2-X_1, X_1-X_2, Y_2-Y_1) \Rightarrow max(|Y_2-Y_1|, |X_2-X_1|)$
那么对于平面上n个点,点对的最大曼哈顿距离,可按照$x_i-y_i$升序排序得到点对序列$(x’,y’)$,再按照$x_i+y_i$升序排序得到点对序列$(x’’,y’’)$,$max(|x_n’-x_1’|+|y_n’-y_1’|, |x_n’’-x_1’’|+|y_n’’-y_1’’|)$便是最大曼哈顿距离。
注意由于至少有三个点,那么如果我们删除的点不属于最大曼哈顿距离的点对。距离不会变化。
我们要删除点,也只会在$(x_1’, y_1’), (x_1’’, y_1’’), (x_n’, y_n’), (x_n’’, y_n’’)$四个点中删除,注意是删除排序前的序列中的点。每删除一个都重新排序获取最大曼哈顿距离。
代码
1 | template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) { |