結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー Min_25
提出日時 2017-05-06 01:59:27
言語 Python2
(2.7.18)
結果
AC  
実行時間 419 ms / 5,000 ms
コード長 1,414 bytes
コンパイル時間 806 ms
コンパイル使用メモリ 7,204 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-09-14 10:14:17
合計ジャッジ時間 2,546 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from fractions import gcd

def solve():
  def extgcd(a, b):
    s, t = 1, 0
    u, v = 0, -1
    while b:
      a, (q, b) = b, divmod(a, b)
      s, u = u, s - q * u
      t, v = v, t - q * v
    return (s, t)

  input = sys.stdin.readline

  Q = int(input())
  for _ in range(Q):
    W, H, D, x2, y2, x1, y1, vx, vy = map(int, input().split())
    if vx < 0:
      x1, x2, vx = W - x1, W - x2, -vx
    if vy < 0:
      y1, y2, vy = H - y1, H - y2, -vy
    if vx == 0 or vy == 0:
      if vy == 0:
        x1, y1 = y1, x1
        x2, y2 = y2, x2
        vx, vy = vy, vx

    hit = False
    for y3 in [y2, 2 * H - y2]:
      if y3 < y1: y3 += 2 * H
      if vx == 0:
        if x1 == x2:
          tn = (y3 - y1)
          td = vy
          if D * td >= tn:
            hit = True
      else:
        for x3 in [x2, 2 * W - x2]:
          if x3 < x1: x3 += 2 * W
          a = 2 * W * vy
          b = 2 * H * vx
          c = vy * (x1 - x3) - vx * (y1 - y3)
          g = gcd(a, b)
          if c % g != 0:
            continue
          a, b, c = a // g, b // g, c // g
          s, t = extgcd(a, b)
          s *= c
          t *= c
          q = min(s // b, t // a)
          s -= b * q
          t -= a * q
          assert(s - b < 0 or t - a < 0)
          tn = (x3 - x1 + 2 * W * s)
          td = vx
          if D * td >= tn:
            hit = True
    print("Hit" if hit else "Miss")

solve()
0