Erect the Fence LeetCode solution in Python

1
class Solution:
2
    """Compute the convex hull of a set of points.
3

4
    Use Andrew's Monotone Chain algorithm, which has order O(N log(N)),
5
    where N is the number of input points.
6
    """
7

8
    def cross(self, p, a, b):
9
        """Return the cross product of the vectors p -> a and p -> b."""
10
        return (a[0] - p[0]) * (b[1] - p[1]) - (a[1] - p[1]) * (b[0] - p[0])
11

12
    def _convex_hull_monotone_chain(self, points):
13
        """Compute the convex hull of a list of points.
14

15
        Use Andrew's Monotone Chain algorithm, which is similar to Graham Scan,
16
        except that it doesn't require sorting the points by angle.  This algorithm
17
        takes O(N log(N)) time, where N is len(points).
18
        """
19
        # Ensure all points are unique, and sort lexicographically.
20
        points = list(sorted(set(points)))
21

22
        # If there are fewer than three points, they must form a hull.
23
        if len(points) <= 2:
24
            return points
25

26
        # Compute the lower and upper portion of the hull.
27
        lower, upper = [], []
28
        for out, it in ((lower, points), (upper, reversed(points))):
29
            for p in it:
30
                while len(out) >= 2 and self.cross(out[-2], out[-1], p) > 0:
31
                    out.pop()
32
                out.append(p)
33

34
        # Concatenate the upper and lower hulls.  Remove the last point from each
35
        # because those points are duplicated in both upper and lower.
36
        return lower[:-1] + upper[:-1]
37

38
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
39
        """
40
        Find the convex hull of a collection of points.
41
        Return a list of indices of points forming the hull in clockwise order,
42
        starting with the leftmost point.
43
        """
44
        # Convert input points to tuples.
45
        points = [tuple(p) for p in trees]
46
        ans = set()
47
        for point in self._convex_hull_monotone_chain(points):
48
            ans.add(point)
49
        return ans