问题描述

给定在 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

所有的点都是不同的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-area-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 将所有点加入到一个集合中，后面可以通过该集合来判断某个点是否出现在 points 中
• 对于任意两个点 (x1, y1)、(x2, y2)，判断是否存在以它们为对角线的矩形。如果存在，则计算面积。在以下两种情况中，不存在以它们为对角线的矩形：
  • x1 等于x2 或 y1 等于 y2
  • (x1, y2) 不在集合中 或 (x2, y1) 不在集合中

Python 实现

class Solution(object):
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        s = {(x, y) for x, y in points}
        ans = None

        for i in range(0, len(points) - 1):
            for j in range(i + 1, len(points)):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x1 == x2 or y1 == y2:
                    continue
                if (x1, y2) not in s or (x2, y1) not in s:
                    continue
                area = abs(x1 - x2) * abs(y1 - y2)
                if ans is None or area < ans:
                    ans = area
        return ans or 0