-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
939.py
50 lines (48 loc) · 1.89 KB
/
939.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
__________________________________________________________________________________________________
sample 208 ms submission
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
n = len(points)
nx = len(set(x for x, y in points))
ny = len(set(y for x, y in points))
if nx == n or ny == n:
return 0
p = collections.defaultdict(list)
if nx > ny:
for x, y in points:
p[x].append(y)
else:
for x, y in points:
p[y].append(x)
lastx = {}
res = float('inf')
for x in sorted(p):
p[x].sort()
for i in range(len(p[x])):
for j in range(i):
y1, y2 = p[x][j], p[x][i]
if (y1, y2) in lastx:
res = min(res, (x - lastx[y1, y2]) * (y2 - y1))
lastx[y1, y2] = x
return res if res < float('inf') else 0
__________________________________________________________________________________________________
sample 13352 kb submission
from collections import defaultdict
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
pool = defaultdict(set)
for point in points:
pool[point[0]].add(point[1])
print(pool)
minimum = float('inf')
for x1 in pool:
for x2 in pool:
if x1 == x2: continue
intersection = pool[x1] & pool[x2]
if len(intersection) >= 2:
for y1 in intersection:
for y2 in intersection:
if y1 == y2: continue
minimum = min(minimum, abs(x1 - x2) * abs(y1 - y2))
return minimum if minimum != float('inf') else 0
__________________________________________________________________________________________________