Monotone Chain Convex Hull in Python


  • 0
    class Solution(object):
        def outerTrees(self, points):
            """
            :type points: List[Point]
            :rtype: List[Point]
            """
            if len(points) == 1:
                return points
            def direction(p, q, r):
                return cmp((p.x - r.x) * (q.y - r.y), (p.y - r.y) * (q.x - r.x))
            
            points.sort(key=lambda x:(x.x, x.y))
            upper = []
            lower = []
            for point in points:
                while len(lower) >= 2 and direction(lower[-2], lower[-1], point) < 0:
                    lower.pop()
                lower.append(point)
            
            for point in reversed(points):
                while len(upper) >= 2 and direction(upper[-2], upper[-1], point) < 0:
                    upper.pop()
                upper.append(point)
            
            return list(set(upper[1:] + lower[1:]))
    

  • 0
    L

    What's the logic behind needing an upper and lower?


  • 0

    @livelearn That means all cross products between two vectors are in the same direction which can conclude that it's a convex.


Log in to reply
 

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