美文网首页
939. 最小面积矩形(Python)

939. 最小面积矩形(Python)

作者: 玖月晴 | 来源:发表于2021-04-01 19:59 被阅读0次

    难度:★★★☆☆
    类型:几何
    方法:数学

    题目

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

    给定在 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
    所有的点都是不同的。

    解答

    点以列表的形式给出,我们把它们放在一个集合内。让它们两两组队,要求这两个点在矩形中是不相邻的(横坐标或者纵坐标不相等),看看能不能在集合中再找到两个点,使得这四个点组成矩形(因为只要对顶点确定了,矩形就确定了,另外两个点随之确定),如果可以,更新一下最小面积。最后返回需要的结果。

    class Solution:
        def minAreaRect(self, points):
            st = set([tuple(p) for p in points])
            ans = float("inf")
            for i in range(len(points)):
                for j in range(i + 1, len(points)):
                    (x1, y1), (x2, y2) = points[i], points[j]
                    if x1 != x2 and y1 != y2 and (x1, y2) in st and (x2, y1) in st:
                        ans = min(ans, abs((x1 - x2) * (y1 - y2)))
            return 0 if ans == float("inf") else ans
    

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

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

    相关文章

      网友评论

          本文标题:939. 最小面积矩形(Python)

          本文链接:https://www.haomeiwen.com/subject/lcynqltx.html