給定二維空間中的點列表（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。在這種情況下，公式很容易找到（它只取決於最大距離點所在的象限）。