結果
問題 | No.62 リベリオン(Extra) |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
from math import gcddef 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 == hyg = gcd(vx, vy)vx //= gvy //= gd *= gif vx < 0:vx *= -1mx = w - mxhx = w - hxif vy < 0:vy *= -1my = h - myhy = h - hyif vy == 0:vx, vy = vy, vxmx, my = my, mxhx, hy = hy, hxh, w = w, hif vx == 0:if mx != hx:return Falseelif hy <= my <= hy + d or hy <= 2 * h - my <= hy + d:return Trueelse:return Falsedef ok(mx, my):a = 2 * w * vyb = 2 * h * vxx, y, g = ext_gcd(a, -b)c = vx * (my - hy) - vy * (mx - hx)if c % g != 0:return Falsea //= gb //= gc //= gx *= cy *= ce = x // bx -= b * ey -= a * eif y < 0:e = abs(y) // bx += b * ey += a * et = (mx + 2 * w * x - hx) // vxreturn t <= dfor _ in range(2):for _ in range(2):if ok(mx, my):return Truemx = 2 * w - mxmy = 2 * h - myreturn Falsefor _ in range(int(input())):if solve(*map(int, input().split())):print("Hit")else:print("Miss")