結果
問題 | No.2012 Largest Triangle |
ユーザー | Kiri8128 |
提出日時 | 2021-06-10 02:20:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 957 ms / 2,500 ms |
コード長 | 1,799 bytes |
コンパイル時間 | 1,336 ms |
コンパイル使用メモリ | 87,288 KB |
実行使用メモリ | 118,328 KB |
最終ジャッジ日時 | 2023-09-10 05:43:32 |
合計ジャッジ時間 | 22,842 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
71,540 KB |
testcase_01 | AC | 88 ms
71,544 KB |
testcase_02 | AC | 90 ms
71,620 KB |
testcase_03 | AC | 92 ms
71,888 KB |
testcase_04 | AC | 90 ms
71,568 KB |
testcase_05 | AC | 89 ms
71,468 KB |
testcase_06 | AC | 88 ms
71,856 KB |
testcase_07 | AC | 91 ms
71,824 KB |
testcase_08 | AC | 89 ms
71,752 KB |
testcase_09 | AC | 89 ms
71,400 KB |
testcase_10 | AC | 90 ms
71,548 KB |
testcase_11 | AC | 91 ms
71,452 KB |
testcase_12 | AC | 92 ms
71,804 KB |
testcase_13 | AC | 93 ms
71,496 KB |
testcase_14 | AC | 93 ms
71,680 KB |
testcase_15 | AC | 93 ms
71,892 KB |
testcase_16 | AC | 898 ms
114,208 KB |
testcase_17 | AC | 931 ms
117,508 KB |
testcase_18 | AC | 952 ms
118,328 KB |
testcase_19 | AC | 922 ms
115,444 KB |
testcase_20 | AC | 902 ms
114,516 KB |
testcase_21 | AC | 903 ms
114,440 KB |
testcase_22 | AC | 904 ms
114,268 KB |
testcase_23 | AC | 920 ms
114,588 KB |
testcase_24 | AC | 901 ms
115,064 KB |
testcase_25 | AC | 957 ms
117,812 KB |
testcase_26 | AC | 721 ms
114,892 KB |
testcase_27 | AC | 721 ms
114,804 KB |
testcase_28 | AC | 732 ms
114,600 KB |
testcase_29 | AC | 722 ms
114,768 KB |
testcase_30 | AC | 723 ms
114,840 KB |
testcase_31 | AC | 865 ms
114,536 KB |
testcase_32 | AC | 853 ms
114,696 KB |
testcase_33 | AC | 852 ms
115,644 KB |
testcase_34 | AC | 865 ms
115,376 KB |
testcase_35 | AC | 870 ms
115,460 KB |
testcase_36 | AC | 110 ms
77,528 KB |
testcase_37 | AC | 111 ms
77,476 KB |
testcase_38 | AC | 114 ms
77,268 KB |
testcase_39 | AC | 112 ms
77,304 KB |
testcase_40 | AC | 113 ms
77,256 KB |
testcase_41 | AC | 260 ms
89,376 KB |
ソースコード
import sys input = lambda: sys.stdin.readline().rstrip() from collections import deque class CHT(): # Convex Hull Trick, Sorted Lines, Sorted Queries, Min Query # add_line は a の降順 # query は x の昇順 def __init__(self): self.Q = deque() def calc(self, f, x): return f[0] * x + f[1] def check(self, f1, f2, f3): return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0]) def add_line(self, a, b): f = (a, b) if len(self.Q) and self.Q[-1][0] == a: if self.Q[-1][1] > b: self.Q.pop() else: return while len(self.Q) >= 2 and self.check(self.Q[-2], self.Q[-1], f): self.Q.pop() self.Q.append(f) def query(self, x): while len(self.Q) >= 2 and self.calc(self.Q[0], x) >= self.calc(self.Q[1], x): self.Q.popleft() return self.calc(self.Q[0], x) def calc(n, X): x_y0 = 0 for i, (x, y) in enumerate(X): if y == 0: x_y0 = x del X[i] break ans = 0 if x_y0: may = 0 for x, y in X: may = max(may, abs(y)) ans = abs(x_y0) * may X.sort(key = lambda x: x[1]) cht1 = CHT() for x, y in X: cht1.add_line(-y, x) cht2 = CHT() for x, y in X[::-1]: cht2.add_line(y, -x) X = [(x, y, x / y) for x, y in X] X.sort(key = lambda x: x[2]) for x, y, z in X: ans = max(ans, y * cht1.query(z) if y < 0 else -y * cht2.query(z)) return round(ans) N = int(input()) X = [] for _ in range(N): x, y = map(int, input().split()) X.append((x, y)) print(calc(N, X))