1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def dot(u,v): # u·v,点乘(内积)
return u[0]*v[0]+u[1]*v[1]
def cross(u,v): # u X v,叉乘(外积),逆正顺负
return u[0]*v[1]-u[1]*v[0]
def convex(A,sgn=1): # 离线生成上凸包,sgn=-1 下凸包(注意保证 A[i][1]>=0)
def check(a,b,c):
u = [b[0]-a[0],b[1]-a[1]]
v = [c[0]-b[0],c[1]-b[1]]
return cross(u,v)>=0 if sgn==1 else cross(u,v)<=0
A.sort()
sk = []
for u in A:
while len(sk)>1 and check(sk[-2],sk[-1],u):
sk.pop()
sk.append(u)
return sk
sk = convex([]) # 上凸包:u[1]正求最大、u[1]负求最小,下凸包:u[1]负求最大,u[1]正求最小
u = (0,0)
i = bisect_left(range(len(sk)-1),True,key=lambda i: dot(u,sk[i])>dot(u,sk[i+1]))
|