我用我最喜欢的求凸包写法去写,结果在最大一个点 TLE 了,看来我需要重新学一个常数更小的方法。
from functools import cmp_to_key
class ppt:
def __init__(a,x=0,y=0):
a.x=x
a.y=y
def inp(a):
a.x,a.y=map(float,input().split())
def __sub__(a,b):
return ppt(a.x-b.x,a.y-b.y)
def sq(a):
return (a.x**2+a.y**2)**0.5
def __mul__(a,b):
return a.x*b.y-a.y*b.x
def cmp(a,b):
x=(a-e[0])*(e[0]-b)
if x==0:x=(a-e[0]).sq()-(b-e[0]).sq()
return x
n=int(input())
e=[ppt() for _ in range(n)]
for i in range(n):
e[i].inp()
if e[i].x<e[0].x or (e[i].x==e[0].x and e[i].y>e[0].y):
e[0],e[i]=e[i],e[0]
e[1:]=sorted(e[1:],key=cmp_to_key(cmp))
m=0
for i in range(1,n):
while m>0 and (e[i]-e[m])*(e[m]-e[m-1])>=0:
m-=1
e[m+1],e[i]=e[i],e[m+1]
m+=1
rs=0
m+=1
for i in range(m):
rs+=(e[i]-e[(i+1)%m]).sq()
print(f"{rs:.2f}")