Giả sử chúng ta có một mảng một số điểm trong mặt phẳng XY. Chúng ta phải tìm diện tích hình chữ nhật nhỏ nhất có thể được tạo thành từ những điểm này. Cạnh của hình chữ nhật phải song song với trục X và Y. Nếu chúng ta không thể tạo thành hình chữ nhật, thì trả về 0. Vì vậy, nếu mảng các điểm giống như [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)] . Đầu ra sẽ là 4. Vì hình chữ nhật có thể được tạo ra bằng cách sử dụng các điểm (1, 1), (1, 3), (3, 1) và (3, 3).
Để giải quyết điều này, hãy cho các điểm theo tọa độ x, sao cho các điểm trên các đường thẳng đứng được nhóm lại với nhau. Sau đó, với mỗi cặp điểm trong nhóm như (x, y1) và (x, y2), chúng ta sẽ tìm hình chữ nhật nhỏ nhất có cặp điểm này, là cạnh bên phải nhất của hình chữ nhật sẽ được tạo thành. Chúng ta có thể thực hiện điều này bằng cách theo dõi tất cả các cặp điểm khác, chúng ta đã truy cập trước đây. Cuối cùng trả về diện tích tối thiểu có thể có của hình chữ nhật thu được.
Ví dụ
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)) Đầu ra
Minimum area of rectangle: 4