记录我用 Python 写凸包被卡常的事情
查看原帖
记录我用 Python 写凸包被卡常的事情
260884
WeLikeStudying楼主2024/10/12 10:21

我用我最喜欢的求凸包写法去写,结果在最大一个点 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}")
2024/10/12 10:21
加载中...