Graham's scan in Python3


  • 0
    G
    class Solution:
        def ccw(self, a, b, c):
            return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y)
        
        def outerTrees(self, points):
            """
            :type points: List[Point]
            :rtype: List[Point]
            """
            if len(points) <= 2:
                return points
            points = sorted(points, key=lambda x:[x.x, x.y])
            result = [points[0]]
            used = set()
            for i in range(1, len(points)):
                if len(result) < 2:
                    result.append(points[i])
                    used.add(points[i])
                else:
                    l = len(result)
                    while l >= 2 and self.ccw(result[l-2], result[l-1], points[i]) < 0:
                        used.remove(result[-1])
                        result.pop()
                        l = len(result)
                    result.append(points[i])
                    used.add(points[i])
            for i in range(len(points)-2, -1, -1):
                if points[i] in used:
                    continue
                if len(result) < 2:
                    result.append(points[i])
                else:
                    l = len(result)
                    while l >= 2 and self.ccw(result[l-2], result[l-1], points[i]) < 0:
                        result.pop()
                        l = len(result)
                    result.append(points[i])
            return result[:-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.