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