Python Graham Scan, simple and short


  • 0
    Y
        def outerTrees(self, A):
            """
            :type points: A[Point]
            :rtype: List[Point]
            """
            def comparator(p1,p2):
                if p1.x==p2.x: return p1.y-p2.y
                else: 
                    return p1.x-p2.x
                    
            def onleftside(p0,p1,p2):
                x1,x2=p1.x-p0.x,p2.x-p1.x
                y1,y2=p1.y-p0.y,p2.y-p1.y
                cross=x1*y2-x2*y1
                return cross>0
                
            def findHull(s,p):
                while len(s)>=2 and onleftside(s[-2],s[-1],p):
                    s.pop()
                s.append(p)
            
            n= len(A)
            if n<4: return A
            A.sort(cmp=comparator)
            
            upHull,bottemHull=[A[0]],[A[-1]]
            for i in xrange(1,n):
                findHull(upHull,A[i])
            for i in xrange(n-2,-1,-1):
                findHull(bottemHull,A[i])
    
            for p in bottemHull:
                if p not in upHull:
                    upHull.append(p)
            return upHull
    

Log in to reply
 

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