LeetCode-939 Minimum Area Rectangle

题目链接

题意

求由点集里面的点组成的最小长方形的面积

思路

暴力可过

不暴力的话，有一些基于数据的随机分布的优化，最坏的情况好像也是\(O(n^2)\)，此处不细讲了

代码

class Solution:
    def minAreaRect(self, points):
        s = set()
        ubound = 40000*40000+1
        ans = 40000*40000+1
        for x1, y1 in points:
            for x2, y2 in s:
                if (x1, y2) in s and (x2, y1) in s:
                    calc = abs(x1 - x2) * abs(y1 - y2)
                    if calc and calc < ans:
                        ans = calc
            s.add((x1, y1))
        return 0 if ans==ubound else ans