给定二维空间中的点列表（x [i]，y [i]），我们需要找到两个最远点（曼哈顿距离）。查找二维空间中的两个最远点（曼哈顿距离）
我知道算法，但我不太明白它是如何工作的。
查找以下几点：MAX（X [1] + Y [I]），最大值（-x [I] +值Y [i]），最大值（-y [I] + X [I ]）和max（-x [i] - y [i]）。
计算列表中每个点与前一步骤中选择的四个点之间的距离，并选择最大的点。
有人请解释为什么这个算法是正确的。
我们必须最大化曼哈顿距离，其中P =（X，Y）是任意的从该组固定点
MD = Abs(X - x[i]) + Abs(Y - y[i])
有四种情况：
1所述的最远点是左从P（不严格，x[i]<=X, y[i]<=Y）下来，这样我们就可以打开ABS-括号作为
MD = X - x[i] + Y - y[i]
最大值当达到了n后(-x[i] - y[i])是最大
2所述的最远点是左和上从P，所以
MD = X - x[i] - Y + y[i]
最大值时(-x[i] + y[i])是最大
相同的逻辑是用于右上和右下的情况。因此我们可以看到，任何P（属于该集合）的最远点必须从这四个变体（称为极值点）中选择。
的改写：
如果我们从一组选择任意点P，从它的最远点是极值E.但是从极值的最远点为E1 - 极值呢！ （如果P是极值，它可能是P）。
我不能给你一个超级技术或详细的答案，但直观地说，这是有道理的。
您首先找到角点的原因是因为两点之间的曼哈顿最大距离将始终包含角点。如果不是，那么它只能等于或小于。这使得大型数组无需搜索每个组合，因此您的搜索将更加高效。如果它有助于图片，那么图片上的图片6点。在任何可能的位置上画出4个角点。然后试着想象一下内侧两点与其他角点相距较远的方式。希望这可以帮助。我知道这不是很技术。
让P1 = (x1, y1)和P2 = (x2, y2) s.t. d(P1, P2) = |x1-x2| + |y1-y2|是最大的。
让我们假设例如x1 >= x2和y1 >= y2（其他情况非常相似，您必须使用其他最大点）。然后：
d(P1, P2) = x1 - x2 + y1 - y2 (1)
让P3 = (x3, y3) s.t. x3 + y3是最大的。我们的目标是显示d(P3, P2) >= d(P1, P2)。
根据定义x3 + y3 >= x1 + y1 (2)。由（1）和（2）：
x3 <= x2，则：d(P3, P2) = x2 - x3 + y3 - y2 >= x2 - x3 + (x1 + y1 - x2) - y2 = x1 + y1 - x3 - y2 >= x1 - x2 + y1 - y2 = d(P1, P2)y3 <= y2：对称的情况。x3 >= x2和y3 >= y2：d(P3, P2) = x3 - x2 + y3 - y2 >= x1 - y2 + y1 - y2 = d(P1, P2)。因此d(P3, P2) >= d(P1, P2)和d(P3, P2) <= d(P1, P2)，所以该算法在这种情况下是正确的。
几何证明：让我们来翻译点，以便P2现在是(0, 0)。然后，该组的直径是到达位于最大直径的闭合球上的点的距离。曼哈顿距离的球是正方形，与坐标轴的角度为pi/4。在这种情况下，公式很容易找到（它只取决于最大距离点所在的象限）。