結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:42:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,584 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 87,496 KB
最終ジャッジ日時 2025-06-12 21:46:11
合計ジャッジ時間 1,476 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def solve():
    input = sys.stdin.read().split()
    idx = 0
    Q = int(input[idx])
    idx += 1
    for _ in range(Q):
        W = int(input[idx])
        H = int(input[idx+1])
        D = int(input[idx+2])
        Mx = int(input[idx+3])
        My = int(input[idx+4])
        Hx = int(input[idx+5])
        Hy = int(input[idx+6])
        Vx = int(input[idx+7])
        Vy = int(input[idx+8])
        idx +=9
        
        hit = False
        
        t1 = None
        t2 = None
        if Vx != 0:
            t1_num = Mx - Hx
            t1 = t1_num / Vx
        if Vy != 0:
            t2_num = My - Hy
            t2 = t2_num / Vy
        
        if Vx == 0 and Vy == 0:
            pass
        elif Vx != 0 and Vy != 0:
            if t1 == t2 and t1 >= 0 and t1 <= D:
                hit = True
        elif Vx == 0:
            if Hx == Mx:
                if Vy == 0:
                    if Hy == My:
                        hit = True
                else:
                    if (My - Hy) * Vy >= 0:
                        t = (My - Hy) / Vy
                        if t >=0 and t <= D:
                            hit = True
        else:  # Vy ==0
            if Hy == My:
                if Vx ==0:
                    if Hx == Mx:
                        hit = True
                else:
                    if (Mx - Hx) * Vx >=0:
                        t = (Mx - Hx)/Vx
                        if t >=0 and t <= D:
                            hit = True
        
        if hit:
            print("Hit")
            continue
        
        signs_x = [1, -1]
        signs_y = [1, -1]
        for sign_x in signs_x:
            for sign_y in signs_y:
                a = 2 * W * Vy
                b = -2 * H * Vx
                c_part = (Hx - sign_x * Mx) * Vy - (Hy - sign_y * My) * Vx
                c = c_part
                
                g = math.gcd(a, b)
                if g ==0:
                    if c ==0:
                        pass
                    else:
                        continue
                else:
                    if c % g !=0:
                        continue
                    a_prime = a // g
                    b_prime = b // g
                    c_prime = c // g
                    
                    if a_prime ==0 and b_prime ==0:
                        if c_prime !=0:
                            continue
                        else:
                            k0 = 0
                            m0 =0
                    elif a_prime ==0:
                        if c_prime % b_prime !=0:
                            continue
                        m0 = c_prime // b_prime
                        k0 =0
                    elif b_prime ==0:
                        if c_prime % a_prime !=0:
                            continue
                        k0 = c_prime // a_prime
                        m0 =0
                    else:
                        g2, x, y = extended_gcd(a_prime, b_prime)
                        if g2 !=1:
                            pass
                        k0 = x * c_prime
                        m0 = y * c_prime
                    
                    if Vx ==0 or Vy ==0:
                        if Vx ==0:
                            if a ==0:
                                pass
                            else:
                                pass
                        else:
                            pass
                        pass
                    
                    try:
                        numerator_t = 2 * k0 * W + sign_x * Mx - Hx
                        if Vx ==0:
                            pass
                        else:
                            t = numerator_t / Vx
                    except ZeroDivisionError:
                        continue
                    else:
                        if t <0 or t > D:
                            continue
                        
                        y_t = Hy + Vy * t
                        mirrored_y = 2 * m0 * H + sign_y * My
                        if abs(y_t - mirrored_y) > 1e-9:
                            continue
                        else:
                            hit = True
                            break
            if hit:
                break
        if hit:
            print("Hit")
        else:
            print("Miss")

if __name__ == "__main__":
    solve()
0