結果
問題 |
No.849 yuki国の分割統治
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:53:12 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,764 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 82,888 KB |
実行使用メモリ | 139,008 KB |
最終ジャッジ日時 | 2025-03-20 20:53:48 |
合計ジャッジ時間 | 9,972 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 WA * 1 |
ソースコード
import sys import math from fractions import Fraction from collections import defaultdict 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)] # Calculate determinant det = a * d - b * c if det != 0: # Process for non-zero determinant groups = defaultdict(set) for x, y in points: # Compute x' num_x = d * x - c * y den_x = det g = math.gcd(num_x, den_x) red_num_x = num_x // g red_den_x = den_x // g rem_x = red_num_x % red_den_x # Compute y' num_y = -b * x + a * y den_y = det g = math.gcd(num_y, den_y) red_num_y = num_y // g red_den_y = den_y // g rem_y = red_num_y % red_den_y # Create key key = ((rem_x, red_den_x), (rem_y, red_den_y)) groups_key = key groups[groups_key].add( (x, y) ) print(len(groups)) else: # Process for zero determinant # Find the direction vector g using u=(a,b) if (a, b) == (0, 0): # Use v as direction vector a, b = c, d # Compute gcd of a and b g_val = math.gcd(a, b) if g_val == 0: g_val = 1 if a == 0 and b == 0: pass else: gx = a // g_val gy = b // g_val # Check if g is zero vector if gx == 0 and gy == 0: gx = c // math.gcd(c, d) gy = d // math.gcd(c, d) # Compute h component and s for each point groups = defaultdict(set) for x, y in points: h_comp = gx * y - gy * x # Compute s_numer and s_denom s_numer = gx * x + gy * y s_denom = gx ** 2 + gy ** 2 if s_denom == 0: # This should not happen as per problem statement pass # Reduce s_numer and s_denom g_s = math.gcd(s_numer, s_denom) red_num = s_numer // g_s red_den = s_denom // g_s # Calculate mod mod_num = red_num % red_den if mod_num < 0: mod_num += red_den # Reduce mod_num and red_den g_mod = math.gcd(mod_num, red_den) mod_num_red = mod_num // g_mod mod_den_red = red_den // g_mod # Key is (mod_num_red, mod_den_red) s_key = (mod_num_red, mod_den_red) # Add to group groups[(h_comp, s_key)].add( (x, y) ) print(len(groups)) if __name__ == "__main__": main()