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
| from collections import defaultdict
from math import sqrt
class Solution:
def minAreaFreeRect(self, points):
len_points = len(points)
res = float('inf')
if len_points < 4:
return 0.0
# Use defaultdict to avoid checking whether the key exists
map_points = defaultdict(list)
for i in range(len_points):
for j in range(i + 1, len_points):
dis = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
centerX = (points[j][0] + points[i][0]) / 2
centerY = (points[j][1] + points[i][1]) / 2
key = str(dis) + "+" + str(centerX) + "+" + str(centerY)
map_points[key].append((i, j))
for key in map_points.keys():
if len(map_points[key]) > 1:
list_indices = map_points[key]
for i in range(len(list_indices)):
for j in range(i + 1, len(list_indices)):
p1, _ = list_indices[i]
p2, p3 = list_indices[j]
len1 = sqrt((points[p1][0] - points[p2][0]) ** 2 + (points[p1][1] - points[p2][1]) ** 2)
len2 = sqrt((points[p1][0] - points[p3][0]) ** 2 + (points[p1][1] - points[p3][1]) ** 2)
area = len1 * len2
res = min(res, area)
return res if res != float('inf') else 0.0
|