結果
問題 |
No.2012 Largest Triangle
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:24:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 862 ms / 2,500 ms |
コード長 | 1,804 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 129,572 KB |
最終ジャッジ日時 | 2025-03-20 20:26:14 |
合計ジャッジ時間 | 18,034 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
import sys def cross(o, a, b): return (a[0] - o[0])*(b[1] - o[1]) - (a[1] - o[1])*(b[0] - o[0]) def convex_hull(points): points = sorted(points) lower = [] for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(points): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) return lower[:-1] + upper[:-1] def find_max_projection(hull, direction): low = 0 high = len(hull) - 1 while low < high: mid = (low + high) // 2 current = hull[mid][0] * direction[0] + hull[mid][1] * direction[1] next_val = hull[mid+1][0] * direction[0] + hull[mid+1][1] * direction[1] if current < next_val: low = mid + 1 else: high = mid return low def main(): input = sys.stdin.read().split() idx = 0 n = int(input[idx]) idx +=1 points = [] for _ in range(n): x = int(input[idx]) y = int(input[idx+1]) points.append((x, y)) idx +=2 hull = convex_hull(points) if not hull: print(0) return max_area = 0 for (x, y) in points: direction_d = (y, -x) direction_neg = (-y, x) idx_d = find_max_projection(hull, direction_d) val_d = direction_d[0] * hull[idx_d][0] + direction_d[1] * hull[idx_d][1] idx_neg = find_max_projection(hull, direction_neg) val_neg = direction_neg[0] * hull[idx_neg][0] + direction_neg[1] * hull[idx_neg][1] current_max = max(abs(val_d), abs(val_neg)) if current_max > max_area: max_area = current_max print(max_area) if __name__ == "__main__": main()