結果
問題 | No.2012 Largest Triangle |
ユーザー | chineristAC |
提出日時 | 2022-07-15 22:41:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,318 ms / 2,500 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 1,641 ms |
コンパイル使用メモリ | 87,220 KB |
実行使用メモリ | 101,228 KB |
最終ジャッジ日時 | 2023-09-10 05:49:10 |
合計ジャッジ時間 | 29,744 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 110 ms
74,552 KB |
testcase_01 | AC | 108 ms
74,264 KB |
testcase_02 | AC | 109 ms
74,812 KB |
testcase_03 | AC | 112 ms
74,656 KB |
testcase_04 | AC | 110 ms
74,448 KB |
testcase_05 | AC | 110 ms
74,204 KB |
testcase_06 | AC | 112 ms
74,388 KB |
testcase_07 | AC | 110 ms
74,192 KB |
testcase_08 | AC | 110 ms
74,644 KB |
testcase_09 | AC | 108 ms
74,628 KB |
testcase_10 | AC | 114 ms
74,352 KB |
testcase_11 | AC | 118 ms
78,772 KB |
testcase_12 | AC | 122 ms
78,844 KB |
testcase_13 | AC | 118 ms
78,744 KB |
testcase_14 | AC | 114 ms
78,812 KB |
testcase_15 | AC | 119 ms
78,892 KB |
testcase_16 | AC | 1,126 ms
100,456 KB |
testcase_17 | AC | 1,127 ms
101,108 KB |
testcase_18 | AC | 1,149 ms
100,624 KB |
testcase_19 | AC | 1,149 ms
101,180 KB |
testcase_20 | AC | 1,131 ms
101,228 KB |
testcase_21 | AC | 1,150 ms
100,476 KB |
testcase_22 | AC | 1,093 ms
100,584 KB |
testcase_23 | AC | 1,099 ms
100,500 KB |
testcase_24 | AC | 1,111 ms
100,764 KB |
testcase_25 | AC | 1,138 ms
100,924 KB |
testcase_26 | AC | 1,318 ms
100,480 KB |
testcase_27 | AC | 1,297 ms
100,628 KB |
testcase_28 | AC | 1,297 ms
100,676 KB |
testcase_29 | AC | 1,269 ms
100,488 KB |
testcase_30 | AC | 1,265 ms
100,504 KB |
testcase_31 | AC | 1,197 ms
100,008 KB |
testcase_32 | AC | 1,213 ms
100,244 KB |
testcase_33 | AC | 1,182 ms
99,972 KB |
testcase_34 | AC | 1,170 ms
100,336 KB |
testcase_35 | AC | 1,170 ms
100,356 KB |
testcase_36 | AC | 171 ms
82,280 KB |
testcase_37 | AC | 170 ms
82,324 KB |
testcase_38 | AC | 168 ms
82,600 KB |
testcase_39 | AC | 165 ms
82,024 KB |
testcase_40 | AC | 167 ms
82,304 KB |
testcase_41 | AC | 335 ms
89,368 KB |
ソースコード
import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) local = False N = int(input()) if not local: xy = [tuple(mi()) for i in range(N)] else: xy = [(random.randint(-100,100),random.randint(-100,100)) for i in range(N)] xy.sort() 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), ...]: ソートされた座標list def 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 qs totu = convex_hull(xy) totu.pop() n = len(totu) def f(i,a,b): i %= n x,y = totu[i] return a*y-b*x res = 0 for x,y in xy: l,m,r = 0,n,2*n while r-l >= 3: nl = (l+m)//2 nr = (m+r+1)//2 if f(nl,x,y) < f(m,x,y): l,m,r = l,nl,m elif f(m,x,y) > f(nr,x,y): l,m,r = m,nr,r else: l,m,r = nl,m,nr res = max(res,abs(f(m,x,y))) l,m,r = 0,n,2*n while r-l >= 3: nl = (l+m)//2 nr = (m+r+1)//2 if -f(nl,x,y) < -f(m,x,y): l,m,r = l,nl,m elif -f(m,x,y) > -f(nr,x,y): l,m,r = m,nr,r else: l,m,r = nl,m,nr res = max(res,abs(f(m,x,y))) print(res) if local: check = 0 for x,y in xy: for p,q in xy: check = max(check,abs(x*q-y*p)) print(check)