No.62 リベリオン(Extra)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 17
作問者 : krotonkroton

1 ProblemId : 132 / 出題時の順位表

ノート

この問題は No.61 リベリオン の制約強化版になります。

問題文

2人の魔法少女MamiとHomuraは幅 \(W\) メートル、奥行き \(H\) メートルの密室で銃撃戦を繰り広げていた。

Homuraは時間を止め、同時に最後の一発を発射した。
時間停止した世界ではHomuraと弾丸しか動くことができず、弾丸は壁にあたると入射角と同じ角度で反射し速度を落とすことなく無限に飛び続ける。

Mamiがいる位置を \((Mx, My)\)、Homuraが発砲した位置を \((Hx, Hy)\)、弾丸の発射時の速度ベクトルを \((Vx, Vy)\) とし \(D\) 秒間時間を止めるとき、
\(D\) 秒以内に弾丸がMamiに当たることはあるか判定せよ。

ただしMamiと弾丸の大きさは無視できるものとし、Homuraが弾丸に当たることはないとする。


図: 配置例

入力

\(Q\)
\(W_{1}\) \(H_{1}\) \(D_{1}\) \(Mx_{1}\) \(My_{1}\) \(Hx_{1}\) \(Hy_{1}\) \(Vx_{1}\) \(Vy_{1}\)
\(W_{2}\) \(H_{2}\) \(D_{2}\) \(Mx_{2}\) \(My_{2}\) \(Hx_{2}\) \(Hy_{2}\) \(Vx_{2}\) \(Vy_{2}\)
\(\ldots\)
\(W_{Q}\) \(H_{Q}\) \(D_{Q}\) \(Mx_{Q}\) \(My_{Q}\) \(Hx_{Q}\) \(Hy_{Q}\) \(Vx_{Q}\) \(Vy_{Q}\)

入力は全て整数で与えられる。

  • \(1 \leq Q \leq 10000\) はテストケースの数を表す。
  • 2行目からの \(Q\) 行では \(W, H, D, Mx, My, Hx, Hy, Vx, Vy\) の組が与えられる。
  • \(2\leq W, H\leq 10^9\)
  • \(1 \leq D \leq 10^9\)
  • \(0 < Mx, Hx < W\)
  • \(0 < My, Hy < H\)
  • \(-10^9 \leq Vx, Vy \leq 10^9\)
  • \((Mx, My) \neq (Hx, Hy)\) が保証されている。
  • \((Vx, Vy) \neq (0, 0)\) が保証されている。

出力

各テストケースで弾丸がMamiに当たる場合は「Hit」当たらない場合は「Miss」を出力せよ。末尾に改行をつけること。

サンプル

サンプル1
入力
5
9 9 74 7 6 4 1 -5 2
7 11 30 5 4 5 10 13 8
15 4 17 10 3 12 3 -3 1
3 9 22 2 2 1 1 13 12
8 11 2 6 5 1 9 -2 -4
出力
Miss
Hit
Miss
Miss
Miss
サンプル2
入力
5
2 15 19 1 2 1 4 1 5
5 5 11 3 1 4 2 9 -7
13 6 68 8 2 11 2 -13 0
2 15 90 1 2 1 8 0 -7
11 4 77 9 1 10 1 -6 13
出力
Miss
Miss
Hit
Hit
Miss
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。