在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