本文涉及知识点

数学 曼哈顿距离

LeetCode3102. 最小化曼哈顿距离

给你一个下标从 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 <= 10⁵
  points[i].length == 2
  1 <= points[i][0], points[i][1] <= 10⁸

数学 曼哈顿距离

令pt1和pt2的距离最大 。
一，如果pt1和pt2外，还有最长点对。则删除任意一点多一样。
二，如果p1和pt2外，没有任何点是最长点对，则删除p1,p2都一样。
三，如果p1只和p2是最长点对，pt1和多个点是最长点对。则删除pt1。
四，如果p2只和p1是最长点对，pt2和多个点是最长点对。则删除pt2。
综上所述：值需要考虑删除两种情况：删除pt1,pt2。
一，求pt1,pt2。如果有多对最长点对，求任意一对。
二,求删除pt1后的最大距离ans1。
三，求删除pt2后的最大距离ans2。
答案就是：min(ans1,ans2)
求最大曼哈顿距离的方法：先转成且比雪夫距离。

代码

核心代码

class Solution {
		public:
			int minimumDistance(vector<vector<int>>& points) {
				auto [tmp, i1, i2] = Cal(points, -1);
				auto [ans1, tmp1, tmp2] = Cal(points, i1);
				auto [ans2, tmp3, tmp4] = Cal(points, i2);
				return min(ans1, ans2);
			}
			tuple<int, int, int> Cal(const vector<vector<int>>& points,const int iExclude= -1) {
				vector<pair<int, int>> xs, ys;
				for (int i = 0; i < points.size();i++) {
					if (iExclude == i) { continue; }
					const auto& v = points[i];
					xs.emplace_back(v[0] + v[1], i);
					ys.emplace_back(v[0] - v[1], i);
				}
				sort(xs.begin(), xs.end());
				sort(ys.begin(), ys.end());
				if (ys.back().first - ys.front().first > xs.back().first - xs.front().first) {
					swap(xs, ys);
				}
				return { xs.back().first - xs.front().first ,xs.back().second,xs.front().second };
			}
		};

单元测试

	vector<vector<int>> points;;
		TEST_METHOD(TestMethod11)
		{
			points = { {9,8},{1,8},{3,1},{9,1},{7,7},{3,6} };
			auto res = Solution().minimumDistance(points);
			AssertEx(13, res);
		}
		TEST_METHOD(TestMethod12)
		{
			points = { {3,10},{5,15},{10,2},{4,4} };
			auto res = Solution().minimumDistance(points);
			AssertEx(12, res);
		}
		TEST_METHOD(TestMethod13)
		{
			points = { {3,2},{3,9},{7,10},{4,4},{8,10},{2,7} };
			auto res = Solution().minimumDistance(points);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod14)
		{
			points = { {1,1},{1,1},{1,1},{1,1} };
			auto res = Solution().minimumDistance(points);
			AssertEx(0, res);
		}