Tìm diện tích nhỏ nhất hình chữ nhật từ tập tọa độ cho trước trong C++

Cho tập điểm trên mặt phẳng XY, tìm diện tích nhỏ nhất hình chữ nhật cạnh song song trục tọa độ. Nếu không tạo được trả về 0. Ví dụ [(1,1),(1,3),(3,1),(3,3),(2,2)] → 4.

Nhóm điểm theo tọa độ x. Với mỗi cặp điểm cùng x (x,y1),(x,y2), tìm cặp điểm cùng y1,y2 ở x trước đó để hình thành hình chữ nhật, cập nhật diện tích nhỏ nhất.

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))

Kết quả

Minimum area of rectangle: 4