結果

問題 No.62 リベリオン(Extra)
ユーザー dangodango
提出日時 2023-07-09 21:28:12
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,690 bytes
コンパイル時間 588 ms
コンパイル使用メモリ 87,096 KB
実行使用メモリ 80,608 KB
最終ジャッジ日時 2023-10-01 01:27:46
合計ジャッジ時間 2,251 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 73 ms
71,488 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10 ** 7 * 15)
def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)
def extgcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        y, x = extgcd(b, a % b)
        return (y, x - (a // b) * y)
def mink(a, c):
    if c < 0:
        return (-c + a - 1) // a
    else:
        return -(c // a)
def collision_check(args):
    w, h, d, hx, hy, vx, vy, xs, ys = args
    a = 2 * w * vy
    b = 2 * h * vx
    c = vx * (ys - hy) - vy * (xs - hx)
    g = gcd(a, b)
    if c % g != 0:
        return False
    a_ = a // g
    b_ = b // g
    c_ = c // g
    ax, bx = extgcd(a_, b_)
    minn = mink(2 * w, xs - hx - 1)
    minm = mink(2 * h, ys - hy - 1)
    k = max(mink(b_, c_ * ax - minn), min_k(a_, -c_ * bx - minm))
    n = b_ * k + c_ * ax
    m = a_ * k - c_ * bx
    x = 2 * w * n + xs
    y = 2 * h * m + ys
    return (x - hx) ** 2 + (y - hy) ** 2 <= (vx ** 2 + vy ** 2) * d ** 2
def line_check(args):
    w, d, mx, hx, vx = args
    dist = mx - hx if mx > hx else (w - hx) * 2 + hx - mx
    return dist <= vx * d
def check(args):
    w, h, d, mx, my, hx, hy, vx, vy = args
    if vx < 0:
        return check([w, h, d, w - mx, my, w - hx, hy, -vx, vy])
    elif vy < 0:
        return check([w, h, d, mx, h - my, hx, h - hy, vx,-vy])
    elif vx == 0:
        return (mx == hx) and line_check([h,d ,my ,hy ,vy])
    elif vy == 0:
        return (my == hy) and line_check([w,d ,mx ,hx ,vx])
    else:
        return any(collision_check([w, h, d, hx, hy, vx, vy, xs, ys]) for xs in [mx,mx+(w-mx)*2] for ys in [my ,my+(h-my)*2])
for _ in range(int(input())):
    print("Hit" if check(list(map(int, input().split()))) else "Miss")
0