难度：★★☆☆☆
类型：几何
方法：排列

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定在 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 的答案将视为正确结果。

解答

这道题没有巧办法，只能按部就班使用笨办法解决。

有以下几个知识点需要注意：

矩形的判定规则：对于一个右四个顶点组成的四边形，如果有三个角是直角，那么这个四边形是矩形。

向量垂直的法则：如果两个向量的点积（对应位置的乘积）为零，那么这两个向量垂直。

矩形的面积等于两条相邻边的欧式距离的乘积。

我们寻找所有四个点的排列情况，如果满足以上矩形的判定规则，则将该矩形的面积记录更新在结果ans中。

class Solution:
    def minAreaFreeRect(self, points):

        def vector(point1, point2):
            (x1, y1), (x2, y2) = point1, point2
            return x2-x1, y2-y1

        def is_vertical(vector1, vector2):
            if vector1 == (0, 0) or vector2 == (0, 0):
                return False
            (x1, y1), (x2, y2) = vector1, vector2
            return x1 * x2 + y1 * y2 == 0

        def dist(p1, p2):
            (x1, y1), (x2, y2) = p1, p2
            return ((x1-x2)**2+(y1-y2)**2)**0.5

        ans = float("inf")
        for p1 in points:
            for p2 in points:
                if p1 == p2:
                    continue

                for p3 in points:
                    if p1 == p3 or p2 == p3:
                        continue
                    vector_p1p2, vector_p2p3 = vector(p1, p2), vector(p2, p3)
                    if not is_vertical(vector_p1p2, vector_p2p3):
                        continue

                    for p4 in points:
                        if p4 in [p1, p2, p3]:
                            continue
                        vector_p3p4, vector_p4p1 = vector(p3, p4), vector(p4, p1)
                        if is_vertical(vector_p1p2, vector_p4p1) and is_vertical(vector_p2p3, vector_p3p4):
                            area = dist(p1, p2) * dist(p2, p3)
                            ans = min(ans, area)
        return 0 if ans == float("inf") else ans


s = Solution()
print(s.minAreaFreeRect([[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析