結果
問題 | No.2331 Maximum Quadrilateral |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:46:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,442 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 66,176 KB |
最終ジャッジ日時 | 2024-12-27 02:55:22 |
合計ジャッジ時間 | 3,791 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
n=int(input())xy=[]for _ in range(n):x,y=map(int,input().split())xy.append((x,y))def cross3(a, b, c):return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])# ps = [(x, y), ...]: ソートされた座標listdef convex_hull(ps):qs = []N = len(ps)for p in ps:# 一直線上で高々2点にする場合は ">=" にするwhile len(qs) > 1 and cross3(qs[-1], qs[-2], p) >= 0:qs.pop()qs.append(p)t = len(qs)for i in range(N-2, -1, -1):p = ps[i]while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:qs.pop()qs.append(p)return qsdef calc(L,R,mid):x1,y1=xy[L]x2,y2=xy[R]x3,y3=xy[mid]dx1=x3-x1dy1=y3-y1dx2=x2-x1dy2=y2-y1return -abs(dy1*dx2-dx1*dy2)xy.sort()cxy=convex_hull(xy)[:-1]assert len(cxy)>=3if len(cxy)==3:xy=cxy+xyn=len(xy)ans=0for i in range(3):p=iq=(i+1)%3r=(i+2)%3for j in range(3,n):if xy[j] not in [xy[p],xy[q],xy[r]]:ans=max(ans,-calc(p,q,j)-calc(q,r,j))print(ans)exit()n=len(cxy)xy=cxy+cxydef get(L,R):l=Lr=Rwhile l+2<r:c1=l+(r-l)//3c2=r-(r-l)//3if calc(L,R,c1)<calc(L,R,c2):r=c2else:l=c1ans=10**18for i in range(l,r+1):ans=min(ans,calc(L,R,i))return -ansans=0for i in range(n):for j in range(i+2,n):ans=max(ans,get(i,j)+get(j,i+n))print(ans)