結果
| 問題 |
No.61 リベリオン
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 15:26:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,929 bytes |
| コンパイル時間 | 189 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 86,528 KB |
| 最終ジャッジ日時 | 2025-06-12 15:26:55 |
| 合計ジャッジ時間 | 1,341 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 2 WA * 2 |
ソースコード
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
for s_x in [1, -1]:
for s_y in [1, -1]:
if Vx == 0 and Vy == 0:
continue
if Vx == 0:
numerator = Hx - s_x * Mx
denominator = 2 * W
if denominator == 0:
continue
if numerator % denominator != 0:
continue
a = numerator // denominator
if Vy == 0:
continue
else:
C = (s_y * My - Hy) * Vx - (s_x * Mx - Hx) * Vy
A = 2 * W * Vy
B = -2 * H * Vx
G = math.gcd(A, B)
if C % G != 0:
continue
A_prime = A // G
B_prime = B // G
C_prime = C // G
g, x0, y0 = extended_gcd(A_prime, B_prime)
if (C_prime % g) != 0:
continue
x0 *= (C_prime // g)
y0 *= (C_prime // g)
a0 = x0
b0 = y0
a_gen = a0 + B_prime * 0
b_gen = b0 - A_prime * 0
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx if Vx != 0 else (s_y * My - Hy + b_gen * 2 * H) / Vy
if Vx == 0:
t = (s_y * My - Hy + b_gen * 2 * H) / Vy
if Vy == 0:
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx
if Vx == 0 and Vy == 0:
continue
if t > 0 and t <= D:
hit = True
break
elif Vy == 0:
numerator = Hy - s_y * My
denominator = 2 * H
if denominator == 0:
continue
if numerator % denominator != 0:
continue
b = numerator // denominator
if Vx == 0:
continue
else:
C = (s_y * My - Hy) * Vx - (s_x * Mx - Hx) * Vy
A = 2 * W * Vy
B = -2 * H * Vx
G = math.gcd(A, B)
if C % G != 0:
continue
A_prime = A // G
B_prime = B // G
C_prime = C // G
g, x0, y0 = extended_gcd(A_prime, B_prime)
if (C_prime % g) != 0:
continue
x0 *= (C_prime // g)
y0 *= (C_prime // g)
a0 = x0
b0 = y0
a_gen = a0 + B_prime * 0
b_gen = b0 - A_prime * 0
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx if Vx != 0 else (s_y * My - Hy + b_gen * 2 * H) / Vy
if Vx == 0:
t = (s_y * My - Hy + b_gen * 2 * H) / Vy
if Vy == 0:
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx
if Vx == 0 and Vy == 0:
continue
if t > 0 and t <= D:
hit = True
break
else:
A = 2 * W * Vy
B = -2 * H * Vx
C = (s_y * My - Hy) * Vx - (s_x * Mx - Hx) * Vy
G = math.gcd(A, B)
if C % G != 0:
continue
A_prime = A // G
B_prime = B // G
C_prime = C // G
g, x0, y0 = extended_gcd(A_prime, B_prime)
if (C_prime % g) != 0:
continue
x0 *= (C_prime // g)
y0 *= (C_prime // g)
a0 = x0
b0 = y0
a_gen = a0 + B_prime * 0
b_gen = b0 - A_prime * 0
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx
if Vy != 0:
t_y = (s_y * My - Hy + b_gen * 2 * H) / Vy
if abs(t - t_y) > 1e-9:
continue
if t > 0 and t <= D:
hit = True
break
k_min = None
k_max = None
delta_a = B_prime
delta_b = -A_prime
if delta_a == 0 and delta_b == 0:
continue
if (A_prime == 0 and B_prime == 0):
continue
t = (s_x * Mx - Hx + a_gen * 2 * W) / Vx
if Vy != 0:
t_y = (s_y * My - Hy + b_gen * 2 * H) / Vy
if abs(t - t_y) > 1e-9:
continue
if t > 0 and t <= D:
hit = True
break
if delta_a != 0:
a_prev = a_gen - delta_a
t_prev = (s_x * Mx - Hx + a_prev * 2 * W) / Vx
if t_prev <= t:
k_min = 0
k_max = 1
else:
k_min = -1
k_max = 0
else:
k_min = -1
k_max = 0
for k in range(k_min, k_max + 1):
a = a0 + B_prime * k
b = b0 - A_prime * k
t = (s_x * Mx - Hx + a * 2 * W) / Vx
if Vy != 0:
t_y = (s_y * My - Hy + b * 2 * H) / Vy
if abs(t - t_y) > 1e-9:
continue
if t > 0 and t <= D:
hit = True
break
if hit:
break
if hit:
break
if hit:
print("Hit")
else:
print("Miss")
if __name__ == '__main__':
solve()