動機

居然有閉包!! note: cross往下是負的,cross往上是正的

Sol

cross是a向量的x*b向量的y-a向量的y*b向量的x 把a向量當成基準線,cross是負的就是b向量往下轉,正的就是往上轉

所以只要發現有向量是往下轉的就要把之前的去掉,把這個留下來

def cross(c, a, b):
    return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x)

def solution(A):
    idx = {p:i for i,p in enumerate(A)}
    A.sort(key=lambda xy: xy.x)
    down = []
    up = []

    for p in A:
        while len(down) > 1 and cross(down[-2], down[-1], p) < 0:
            down.pop()
        down.append(p)
    for p in reversed(A):
        while len(up) > 1 and cross(up[-2], up[-1], p) < 0:
            up.pop()
        up.append(p)
    
    ans = set(range(len(A))) - set(map(lambda p: idx[p], up)) - set(map(lambda p: idx[p], down))
    return next(iter(ans)) if ans else -1