我有一個點陣列，我的目標是挑選兩個點，以便使這兩個點（一個代表左下角，另一個代表右上角）形成的矩形的面積最大化。
我可以在O(n^2)中完成這個任務，只需做兩個for回圈并計算每一個可能的面積，但我認為一定有一個更有效的解決方案：
max_area = 0。
for p1 in points:
for p2 in points:
area = p2[0]p2[1] p1[0]p1[1] - p2[1]p1[0] - p2[0] p1[1]
if area > max_area:
max_area = area
很明顯，我想最大化以原點（0,0）為中心的第二個點的面積（所以p2[0]p2[1]），但我不確定如何進行下去。
uj5u.com熱心網友回復：
是的，有一個O(n log n)-時間的演算法（應該有一個元素區分度下限來匹配）。
對于每個p1來說，只需要找到與它有最大矩形面積的p2，然后回傳總體最大的。這可以表示為一個三維極點問題。每個p2產生一個三維點(p2[0], p2[1], p2[0] p2[1]), 每個p1產生一個三維矢量(-p1[0], -p1[1], 1)，我們想使點積最大化（技術上是加上p1[0] p1[1]，但這個常數偏移并不影響答案）。那么我們 "只需 "遵循柯克帕特里克1983年的構造即可。
uj5u.com熱心網友回復：
假設你有一個由四個點組成的矩形。A(左上)，B(右上)，C(右下)和D(左下)。
我們的想法是找到兩個點p1和p2分別最接近B和D。這意味著p1和p2之間的距離是最遠的。
def nearest_point（origin, points）。
nearest = None: 最近的 = None.
mindist = dist(origin, points[0] )
for p in points[1:] 。
d = dist(origin, p)
if mindist > d。
mindist = d
最近的 = p
return nearest
為B和D呼叫它作為起源：
points = [...] 。
p1 = nearest_point(B, points) # one for loop。
p2 = nearest_point(D, points) # 一個回圈。
注意，可以有多個距離原點同樣遠的最近的點（B或D）。在這種情況下，nearest_point()應該回傳一個點的陣列。你必須做兩個嵌套的for回圈來找到最遠的兩個點。
uj5u.com熱心網友回復：
除法和征服。
注意：這個演算法假定矩形是軸對齊的。
- 第1步：將點分成4x4個桶的網格。一些小桶 可能是空的。
- 第2步：使用桶的角，計算出
在非空桶之間的相對角上計算最大面積。這可能會導致
這可能會產生幾對水桶，因為你的作業是用角而不是用點。
還要注意的是，你對左邊的水桶使用左角，對那些b,r,t水桶的底角、右角和頂角也是如此。這就是為什么網格的大小要用偶數的原因。 - 第3步：將第2步中選擇的每個桶重新組合成一個新的、更小的、4x4的網格。
- 重復步驟2&3，直到你只得到一對桶，每個桶中只包含一個點。
我沒有計算這個演算法的復雜性。似乎是O(n log(n))。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/332563.html
標籤：
上一篇：`awsecsexecute-command`的結果是`TargetNotConnectedException``由于內部錯誤，執行命令失敗`。