最小面积矩形 II

难度: Medium

给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

示例 1：

输入：[[1,2],[2,1],[1,0],[0,1]]
输出：2.00000
解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。

示例 2：

输入：[[0,1],[2,1],[1,1],[1,0],[2,0]]
输出：1.00000
解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。

示例 3：

输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0
解释：没法从这些点中组成任何矩形。

示例 4：

输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出：2.00000
解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。

提示：

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
与真实值误差不超过 10^-5 的答案将视为正确结果。

Submission

运行时间: 114 ms

内存: 0.0 MB

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        # find mid for each pair of points
        # record set of (mid_x, mid_y, length) as key, list of (x, y) as values
        min_area = inf
        maps = dict()
        for index, [x0, y0] in enumerate(points):
            for j in range(index + 1, len(points)):
                mid_x = (x0 + points[j][0])/2
                mid_y = (y0 + points[j][1])/2
                dist = (x0 - points[j][0])**2 + (y0 - points[j][1])**2
                
                for (x, y) in maps.get((mid_x, mid_y, dist), []):
                    area = sqrt(((x - x0)**2 + (y - y0)**2)*((x - points[j][0])**2 + (y - points[j][1])**2))
                    min_area = min(area, min_area)
                if maps.get((mid_x, mid_y, dist)) == None:
                    maps[(mid_x, mid_y, dist)] = []
                maps[(mid_x, mid_y, dist)].append([x0, y0])
        
        if min_area == inf:
            return 0
        return min_area

Explain

这个题解的思路是枚举每对点组成的对角线中点，并记录中点坐标、对角线长度和对应的点。对于每个中点，如果找到另一对点也以其为中点且对角线长度相等，则可以计算出由这4个点组成的矩形面积。在所有可能的矩形中取最小面积。如果没有找到任何矩形，则返回0。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        # 初始化最小面积为正无穷
        min_area = inf
        # 用于存储中点信息的字典
        maps = dict()
        # 枚举每对点
        for index, [x0, y0] in enumerate(points):
            for j in range(index + 1, len(points)):
                # 计算中点坐标
                mid_x = (x0 + points[j][0])/2
                mid_y = (y0 + points[j][1])/2
                # 计算对角线长度的平方
                dist = (x0 - points[j][0])**2 + (y0 - points[j][1])**2
                
                # 枚举以当前中点为中心的另一对点
                for (x, y) in maps.get((mid_x, mid_y, dist), []):
                    # 计算矩形面积
                    area = sqrt(((x - x0)**2 + (y - y0)**2)*((x - points[j][0])**2 + (y - points[j][1])**2))
                    # 更新最小面积
                    min_area = min(area, min_area)
                # 将当前点加入对应中点的列表中
                if maps.get((mid_x, mid_y, dist)) == None:
                    maps[(mid_x, mid_y, dist)] = []
                maps[(mid_x, mid_y, dist)].append([x0, y0])
        
        # 如果没有找到任何矩形，返回0
        if min_area == inf:
            return 0
        return min_area

Explore

在本算法中，对于每对点，我们只是计算它们的中点和对角线长度。这两点之间的连线确实可以是对角线，但也可能只是矩形的一条边或者只是任意两点。由于我们是在查找具有相同中点和对角线长度的另外两点，只有当这两对点确实满足对角线的条件时（即形成的四个点能够构成矩形），我们才会计算面积。因此，算法设计是在保证只有形成矩形的四点组才被计算面积。

是的，使用浮点数作为字典中的键值确实可能会引入精度问题。浮点数的计算可能会有轻微的误差，这可能导致本应该被认为是相同的中点和长度被误判为不同。为了减少这种误差，可以考虑使用整数运算（例如通过缩放和四舍五入到整数），或者使用特定容差来比较浮点数键的相等性。

在计算矩形面积时使用叉乘，是因为这四个点可能不会构成轴对齐矩形，而是任意角度的矩形。叉乘公式可以用来计算向量组成的平行四边形的面积，这在任意角度的矩形中特别有用。直接计算长和宽的乘积在非轴对齐矩形中计算不正确，因此使用向量叉乘是更通用的方法。

如果点集中包含重复的点，可能会导致计算中的一些异常情况，比如重复计算相同的矩形面积，或者错误地认为重复点构成的‘矩形’的面积为0。这种情况应该在实现算法时进行处理，例如通过集合或其他方式先去除重复点，或者在算法中加入检查以确保不会错误地计算这样的重复点对。