結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー rin204
提出日時 2023-02-15 02:59:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 343 ms / 5,000 ms
コード長 1,651 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 79,828 KB
最終ジャッジ日時 2024-07-17 14:05:54
合計ジャッジ時間 2,230 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd

def ext_gcd(a, b):
    """
    return (x, y, gcd(a, b)) s.t. ax + by = gcd(a, b)
    """
    if a == 0:
        return (0, 1, b)
    else:
        X, Y, g = ext_gcd(b % a, a)
        return (Y - b // a * X, X, g)

def solve(w, h, d, mx, my, hx, hy, vx, vy):
    if vx == 0 and vy == 0:
        return mx == hx and my == hy
            
    g = gcd(vx, vy)
    vx //= g
    vy //= g
    d *= g

    if vx < 0:
        vx *= -1
        mx = w - mx
        hx = w - hx

    if vy < 0:
        vy *= -1
        my = h - my
        hy = h - hy

    if vy == 0:
        vx, vy = vy, vx
        mx, my = my, mx
        hx, hy = hy, hx
        h, w = w, h

    if vx == 0:
        if mx != hx:
            return False
        elif hy <= my <= hy + d or hy <= 2 * h - my <= hy + d:
            return True
        else:
            return False

    def ok(mx, my):
        a = 2 * w * vy
        b = 2 * h * vx
        x, y, g = ext_gcd(a, -b)
        c = vx * (my - hy) - vy * (mx - hx)
        if c % g != 0:
            return False
        a //= g
        b //= g
        c //= g
        x *= c
        y *= c
        e = x // b
        x -= b * e
        y -= a * e
        if y < 0:
            e = abs(y) // b
            x += b * e
            y += a * e
        t = (mx + 2 * w * x - hx) // vx
        return t <= d
        

    for _ in range(2):
        for _ in range(2):
            if ok(mx, my):
                return True

            mx = 2 * w - mx
        my = 2 * h - my

    return False

for _ in range(int(input())):
    if solve(*map(int, input().split())):
        print("Hit")
    else:
        print("Miss")
0