結果
問題 |
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 sys from math import gcd input = sys.stdin.readline MOD = 10 ** 9 + 7 class Vector2: def __init__(self, x: int, y: int): self.x = x self.y = y def __lt__(self, other): return area(self, other) > 0 def area(v1: Vector2, v2: Vector2) -> int: return v1.x * v2.y - v1.y * v2.x n = int(input()) vectors = [] for _ in [0] * n: x, y = map(int, input().split()) if(x == 0 and y == 0): continue if(y < 0): x, y = -x, -y vectors.append(Vector2(x, y)) vectors.sort() s, bh = 0, 0 lx, ly = 0, 0 for v in vectors: v1 = Vector2(lx, ly) v2 = Vector2(lx + v.x, ly + v.y) s += area(v1, v2) % MOD s %= MOD bh += gcd(v.x, v.y) bh %= MOD lx, ly = v2.x, v2.y ans = (s + bh + 1) % MOD print(ans)