結果
問題 |
No.1144 Triangles
|
ユーザー |
|
提出日時 | 2023-12-29 15:17:02 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,189 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 91,204 KB |
最終ジャッジ日時 | 2024-09-27 16:07:38 |
合計ジャッジ時間 | 34,455 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 5 WA * 20 |
ソースコード
from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.readline N = int(input()) XY = [tuple(map(int,input().split())) for _ in range(N)] mod = 10**9 + 7 S = 0 for i in range(N-2): xi,yi = XY[i] xy = [] for j in range(i+1,N): xj,yj = XY[j] xt,yt = xj-xi,yj-yi xy.append((math.atan2(yt,xt),xt,yt)) xy.sort() SY = list(accumulate([0]+ [x for _,x,_ in xy])) SX = list(accumulate([0]+ [x for _,_,x in xy])) n = len(xy) for j in range(n-1): _,xj,yj = xy[j] is_ok = lambda X: (xj*X[2] - yj*X[1])>=0 y = n-1 x = j if is_ok(xy[y]): S = (S + xj*(SX[y+1] - SX[j]) - yj*(SY[y+1] - SY[j]) )%mod continue while y-x>1: mid = (y+x)//2 if is_ok(xy[mid]): x = mid else: y = mid S = (S + xj*(SX[x+1] - SX[j]) - yj*(SY[x+1] - SY[j]) )%mod print(S)