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:
            for point in reversed(points):
                while len(upper) >= 2 and direction(upper[-2], upper[-1], point) < 0:
            return list(set(upper[1:] + lower[1:]))

  • 0

    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.