给定在 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. 1 <= points.length <= 50
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. 所有的点都是不同的。
5. 与真实值误差不超过 10^-5 的答案将视为正确结果。

解题思路

首先想到的解法就是暴力破解，我们先找三个点，首先判断这三个点是不是可以构成直角三角形，如果可以的话，我们再去确定第四个点

• $x_4=x_1+x_3-x_2$
• $y_4=y_1+y_3-y_2$

我们要判断这个坐标是不是在数组中，如果在的话，我们就确定了一个矩形，那么我们就可以计算面积。以此类推，计算所有矩形的面积，去最后所有矩形面积的最小值即可。

class Solution:
    def minAreaFreeRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        res = float('inf')
        mem = set(map(tuple, points))
        def dis(p1, p2):
            return (p1[0]-p2[0])**2 + (p1[1] - p2[1])**2
        
        for (x1, y1) in points:
            for (x2, y2) in points:
                if x1 == x2 and y1 == y2:
                    continue
                for (x3, y3) in points:
                    d1 = dis((x1,y1), (x2,y2))
                    d2 = dis((x1,y1), (x3,y3))
                    d3 = dis((x2,y2), (x3,y3))
                    if d1 + d3 != d2:
                        continue
                    x4 = x1+x3-x2
                    y4 = y1+y3-y2
                    if (x4,y4) not in mem:
                        continue
                        
                    area = pow(d1, 0.5) * pow(d3, 0.5)
                    if area > 0:
                        res = min(res, area)
        
        return res if res != float('inf') else 0  

但是这种做法超时了。还有一种暴力破解的思路，就是现将所有四个点的组合枚举出来，然后判断这四个点是不是可以构成矩形，如果可以的话，计算面积，取所有面积的最小值即可。关于如何判断矩形，可以看这篇判断四个点是否可以构成矩形（优雅的解法！！！）。有没有什么更好的解法呢？我们可以先取出三个点的组合，然后假设这三个点可以构成矩形（并且假设其中一组点是对角），再通过上列中的两个公式求解出第四个点的位置，最后通过向量点积确定是否存在直角，如果存在，那么这个矩形就存在，否则的话矩形不存在。

class Solution:
    def minAreaFreeRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        points = set(map(tuple, points))

        res = float('inf')
        for p1, p2, p3 in itertools.combinations(points, 3):
            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]
            if p4 in points:
                v21 = p2[0] - p1[0], p2[1] - p1[1]
                v31 = p3[0] - p1[0], p3[1] - p1[1]
                if abs(v21[0] * v31[0] + v21[1] * v31[1]) < 1e-5:
                    area = abs(v21[1] * v31[0] - v21[0] * v31[1])
                    if area < res:
                        res = area

        return res if res != float('inf') else 0

通过向量计算的方式，我们加快了速度。但是这种算法依旧是O(n^3)级别的，有没有更好的？对于最后一个例子

我们可以先取出连个点，然后计算两个点的中点，我们建立一个dict存放相同斜率点的中点。

然后我们遍历dict，然后从dict.val中再取出两个点，这两个点一定来自于相同斜率的两边，我们再计算这两个点的斜率，如果和之前的边斜率相垂直，那么原来的两边（四个点）必能构成矩形。按照此法计算所有dict中的值，最后取面积的最小值即可。

class Solution:
    def minAreaFreeRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        points = [complex(*point) for point in sorted(points)]
        mem = collections.defaultdict(list)
        for p, q in itertools.combinations(points, 2):
            mem[q - p].append((p + q) / 2)
            
        res = float('inf')
        for v1, mid_points in mem.items():
            for a, b in itertools.combinations(mid_points, 2):
                v2 = a - b
                if abs(v1.real * v2.real + v1.imag * v2.imag) < 1e-5:
                    res = min(res, abs(v1) * abs(v2))
                    
        return res if res != float('inf') else 0

reference:

https://leetcode.com/problems/minimum-area-rectangle-ii/solution/

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！