LeetCode-939 Minimum Area Rectangle

题目链接

题意

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

思路

暴力可过

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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