結果
問題 | No.1999 Lattice Teleportation |
ユーザー |
![]() |
提出日時 | 2022-07-03 01:14:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 735 ms / 2,000 ms |
コード長 | 707 bytes |
コンパイル時間 | 417 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 88,492 KB |
最終ジャッジ日時 | 2024-11-28 01:20:23 |
合計ジャッジ時間 | 13,996 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
from math import gcd mod = 10**9+7 class Point: def __init__(self, px, py): self.px = px self.py = py def __lt__(self, other): return crs(self, other) > 0 def crs(p1, p2): return p1.px * p2.py - p1.py * p2.px N = int(input()) vec = [] for _ in range(N): A,B = map(int,input().split()) if A == 0 and B == 0: continue if B < 0: A *= -1 B *= -1 vec.append(Point(A, B)) vec.sort() EdgePoint = 0 Area = 0 x,y = 0,0 for v in vec: a = Point(x, y) b = Point(x+v.px, y+v.py) Area += crs(a, b) Area %= mod EdgePoint += gcd(v.px, v.py) EdgePoint %= mod x = b.px y = b.py print((Area + EdgePoint + 1) % mod)