結果
問題 |
No.849 yuki国の分割統治
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:11:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,296 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 104,084 KB |
最終ジャッジ日時 | 2025-04-16 16:16:50 |
合計ジャッジ時間 | 5,323 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 WA * 1 |
ソースコード
import sys import math def main(): a, b, c, d = map(int, sys.stdin.readline().split()) N = int(sys.stdin.readline()) points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)] D = a * d - b * c if D != 0: D_abs = abs(D) groups = {} for x, y in points: s = (d * x - c * y) % D_abs t = (-b * x + a * y) % D_abs key = (s, t) if key not in groups: groups[key] = 0 groups[key] += 1 print(len(groups)) else: # Determine the basis vector (u, v) from (a, b) if a == 0 and b == 0: # This case is impossible due to input constraints pass g = math.gcd(a, b) u = a // g v = b // g # Normalize the basis vector if v < 0 or (v == 0 and u < 0): u = -u v = -v groups = {} for x, y in points: vertical = u * y - v * x temp = x * u + y * v mod = u * u + v * v base = temp % mod if mod != 0 else 0 key = (vertical, base) if key not in groups: groups[key] = 0 groups[key] += 1 print(len(groups)) if __name__ == '__main__': main()