資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢給定座標集的矩形最小面積
假設我們有一個 XY 平面中一些點的陣列。我們必須找到可以從這些點形成的矩形的最小面積。矩形的邊應平行於 X 和 Y 軸。如果我們無法形成矩形，則返回 0。因此，如果點的陣列類似於 [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)]。輸出將為 4。因為可以使用點 (1, 1), (1, 3), (3, 1) 和 (3, 3) 形成矩形。
為了解決這個問題，請按 x 座標給出點，以便將直線上垂直線上的點組合在一起。然後，對於組中每一對點，例如 (x, y1) 和 (x, y2)，我們將找到具有這對點作為要形成的矩形的右邊緣的最小矩形。我們可以透過跟蹤之前訪問過的所有其他點對來做到這一點。最後返回獲得的矩形的最小可能面積。
示例
import collections
def findMinArea(Arr):
columns = collections.defaultdict(list)
for x, y in Arr:
columns[x].append(y)
lastx = {}
ans = float('inf')
for x in sorted(columns):
col = columns[x]
col.sort()
for j, y2 in enumerate(col):
for i in range(j):
y1 = col[i]
if (y1, y2) in lastx:
ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
lastx[y1, y2] = x
if ans < float('inf'):
return ans
else:
return 0
A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print('Minimum area of rectangle:',findMinArea(A))輸出
Minimum area of rectangle: 4
更新於: 2019-12-18
340 次檢視
廣告