leetcode 939. 最小面積矩形

給定在 xy 平面上的一組點，确定由這些點組成的矩形的最小面積，其中矩形的邊平行于 x 軸和 y 軸。

如果沒有任何矩形，就傳回 0。

示例 1：

輸入：[[1,1],[1,3],[3,1],[3,3],[2,2]]

輸出：4

示例 2：

輸入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

輸出：2

提示：

1 <= points.length <= 500

0 <= points[i][0] <= 40000

0 <= points[i][1] <= 40000

所有的點都是不同的。

分析，可以采用一個set資料結構，set查找的時間複雜度是O(1)，設矩形對角線亮點坐标分别為(x1,y1)和(x2,y2)，那如果(x1,y2)和(x2,y1)也在points中，則可以構成一個矩形。

源代碼如下：

class Solution(object):
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if len(points)<4:
            return 0
        points_distinct = set()
        points_distinct.add((points[0][0], points[0][1]))
        minArea=0x7fffffff
        for i in range(1, len(points)):
            x1,y1=points[i][0],points[i][1]
            for x2,y2 in points_distinct:
                if (x1,y2) in points_distinct and (x2,y1) in points_distinct:
                    area=abs(x1-x2)*abs(y1-y2)
                    if area>0 and area<minArea:
                        minArea=area
            points_distinct.add((x1,y1))
        if minArea==0x7fffffff:  #沒有矩形
            return 0
        else:
            return minArea