Erect the Fence

Intuition

Solution

class Solution:
    @staticmethod
    def cross(a, b, c):
        v1 = [b[0] - a[0], b[1] - a[1]]
        v2 = [c[0] - b[0], c[1] - b[1]]
        return v1[0] * v2[1] - v1[1] * v2[0]

    @staticmethod
    def slope(a, b):
        if a[0] == b[0]:
            return float('inf')
        return (b[1] - a[1]) / (b[0] - a[0])

    def outerTrees(self, points: List[List[int]]) -> List[List[int]]:
        """
        Basically a geometry problem. Cross and slope is necessary.
        """
        start = min(points, key=lambda p: (p[0], p[1]))
        points.pop(points.index(start))
        ans = [start]
        points.sort(
            key=lambda p: (self.slope(start, p), -p[1], p[0]),
            reverse=True)
        for p in points:
            ans.append(p)
            while len(ans) > 2 and self.cross(ans[-3], ans[-2], ans[-1]) > 0:
                ans.pop(-2)
        return ans