結果

問題 No.849 yuki国の分割統治
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0