在C ++中使用给定的坐标集查找矩形的最小面积

Z时代
2024-01-10
分类：综合

假设我们在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))