結果
問題 | No.2012 Largest Triangle |
ユーザー |
👑 |
提出日時 | 2022-07-15 22:10:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 962 ms / 2,500 ms |
コード長 | 942 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 100,948 KB |
最終ジャッジ日時 | 2024-06-27 21:20:47 |
合計ジャッジ時間 | 21,909 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
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)qs.pop()return qsn = int(input())xy = [list(map(int, input().split())) for _ in range(n)]xy.sort()xy = convex_hull(xy)n = len(xy)xy += xydef S(i, j):return abs(xy[i][0] * xy[j][1] - xy[i][1] * xy[j][0])ans = 0r = 1for l in range(n):bef = S(l, r)while S(l, r + 1) >= bef:bef = S(l, r + 1)r += 1ans = max(ans, bef)print(ans)