Minimum Area Rectangle II LeetCode solution in Python

1
class Solution:
2
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
3
        N = len(points)
4

5
        seen = set()
6
        for point in points:
7
            seen.add(tuple(point))
8

9
        # length^2
10
        def length2(a, b):
11
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
12

13
        best = 1e30
14
        for i in range(N):
15
            for j in range(N):
16
                if i == j:
17
                    continue
18

19
                lij = length2(points[i], points[j])
20
                for k in range(N):
21
                    if i == k or j == k:
22
                        continue
23

24
                    # given i->j line, add to k to find l
25
                    dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]
26

27
                    pl = (points[k][0] + dx, points[k][1] + dy)
28
                    if pl not in seen:
29
                        continue
30

31
                    lik = length2(points[i], points[k])
32
                    ljk = length2(points[j], points[k])
33

34
                    lil = length2(points[i], pl)
35
                    ljl = length2(points[j], pl)
36
                    lkl = length2(points[k], pl)
37

38
                    if lij == lkl and lik == ljl and lil == ljk:
39
                        best = min(
40
                            best, sqrt(lij * lik * lil) / sqrt(max(lij, lik, lil))
41
                        )
42

43
        if best >= 1e29:
44
            return 0
45
        return best