結果
問題 | No.1999 Lattice Teleportation |
ユーザー |
![]() |
提出日時 | 2024-12-02 15:08:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 597 ms / 2,000 ms |
コード長 | 784 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 89,568 KB |
最終ジャッジ日時 | 2024-12-02 15:08:47 |
合計ジャッジ時間 | 11,366 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
import sysfrom math import gcdinput = sys.stdin.readlineMOD = 10 ** 9 + 7class Vector2:def __init__(self, x: int, y: int):self.x = xself.y = ydef __lt__(self, other):return area(self, other) > 0def area(v1: Vector2, v2: Vector2) -> int:return v1.x * v2.y - v1.y * v2.xn = int(input())vectors = []for _ in [0] * n:x, y = map(int, input().split())if(x == 0 and y == 0):continueif(y < 0):x, y = -x, -yvectors.append(Vector2(x, y))vectors.sort()s, bh = 0, 0lx, ly = 0, 0for v in vectors:v1 = Vector2(lx, ly)v2 = Vector2(lx + v.x, ly + v.y)s += area(v1, v2) % MODs %= MODbh += gcd(v.x, v.y)bh %= MODlx, ly = v2.x, v2.yans = (s + bh + 1) % MODprint(ans)