動機
居然有閉包!! 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