凸包算法之Graham扫描法

今天新接触的一个算法，非常好理解哈哈，实现起来也挺方便的

我是看https://www.pianshen.com/article/763090525/这个博客学的，感谢这位兄弟的分享

我的代码如下：

def convexhull(points:List[Tuple[int,int]])->List[Tuple[int,int]]:
    def left_or_right(x1,y1,x2,y2,x,y):
        tmp = (y1-y2) * x + (x2-x1) * y + x1 * y2 - x2 * y1
        return tmp
    if len(points)<=3:
        return points.copy()
    points = sorted(points,key=lambda point:point[1])
    tx,ty = points[0]
    def cmp_points_atan2(point1,point2):
        a = math.atan2(point1[1]-ty,point1[0]-tx)
        b = math.atan2(point2[1]-ty,point2[0]-tx)
        if a!=b:
            return a-b
        da = (point1[1]-ty)**2+(point1[0]-tx)**2
        db = (point2[1]-ty)**2+(point2[0]-tx)**2
        return da-db
    points.sort(key=cmp_to_key(cmp_points_atan2))
    stack = deque()
    stack.append(points[0])
    stack.append(points[1])
    stack.append(points[2])
    for i in range(3,len(points)):
        pc = points[i]
        while len(stack)>=2:
            pa = stack[-2]
            pb = stack[-1]
            if left_or_right(pa[0],pa[1],pc[0],pc[1],pb[0],pb[1])<=0:
                break
            else:
                stack.pop()
        stack.append(pc)
    ret = list(stack)
    return ret

代码临时乱写的，没什么意义。主要是算法的思想理解了就好。log(n)*n的时间复杂度还是挺给力的