#include using namespace std; using ll = long long; // -------------------------------------------------------- template T floor(T a, T b) { if (b < 0) { return floor(T(-a), T(-b)); } assert(b > 0); return (a > 0 ? T(a / b) : T((a - b + 1) / b)); } // -------------------------------------------------------- // References: // // // 線形ディオファントス方程式 // x + by = c の整数解の一つ (x_0, y_0) を求める // 整数解が求まらなければ false を返す // - ★ a = 0 または b = 0 の場合、結果の取り扱いに注意! ★ // - O(log (a + b)) // - 一般解(k は整数) // x = x_0 + k * (b / g) // y = y_0 - k * (a / g) template bool linear_diophantine_equation (T a, T b, T c, T& x_0, T& y_0, T& g) { auto extgcd = [](T a, T b, T& x, T& y) { auto _extgcd = [](auto&& self, T a, T b, T& x, T& y) -> T { if (b == 0) { x = 1; y = 0; return a; } T g = self(self, b, a % b, y, x); y -= (a / b) * x; return g; }; T g = _extgcd(_extgcd, a, b, x, y); if (g < 0) { g = -g; x = -x; y = -y; } return g; }; if (a == 0 && b == 0) { if (c != 0) { return false; } x_0 = y_0 = g = 0; } else if (a == 0) { if (c % b != 0) { return false; } x_0 = 0; y_0 = c / b; g = abs(b); } else if (b == 0) { if (c % a != 0) { return false; } x_0 = c / a; y_0 = 0; g = abs(a); } else { T x_g, y_g; g = extgcd(a, b, x_g, y_g); if (c % g) { return false; } x_0 = x_g * (c / g); y_0 = y_g * (c / g); } return true; } #if 1 // Reference: https://boostjp.github.io/tips/multiprec-int.html #include typedef boost::multiprecision::cpp_int bint; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int Q; cin >> Q; while (Q--) { bint W, H, D, Mx, My, Hx, Hy, Vx, Vy; cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy; if (Vx < 0) { Vx = -Vx; Hx = W - Hx; Mx = W - Mx; } if (Vy < 0) { Vy = -Vy; Hy = H - Hy; My = H - My; } bool ok = false; bint a = +2*W*Vy; bint b = -2*H*Vx; vector Mx_list = {Mx, 2*W - Mx}; vector My_list = {My, 2*H - My}; for (auto mx : Mx_list) { for (auto my : My_list) { bint c = Vx*(my-Hy) - Vy*(mx-Hx); bint x_0, y_0, g; bool res = linear_diophantine_equation(a, b, c, x_0, y_0, g); if (not res) continue; bint x, y; if (a == 0 || b == 0) { x = x_0; y = y_0; } else { bint kx = floor(bint(+Hx - mx - 2*W*x_0), bint(b / g * 2*W)); bint ky = floor(bint(-Hy + my + 2*H*y_0), bint(a / g * 2*H)); bint k = min(kx, ky); x = x_0 + k * (b / g); y = y_0 - k * (a / g); } bint X = mx + 2*W*x; bint Y = my + 2*H*y; if (not (Hx <= X && X <= Hx + Vx * D)) continue; if (not (Hy <= Y && Y <= Hy + Vy * D)) continue; ok = true; } } string ans = (ok ? "Hit" : "Miss"); cout << ans << '\n'; } return 0; } // Verify: https://yukicoder.me/problems/no/62 #endif #if 0 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); ll a, b; cin >> a >> b; ll x_0, y_0, g; bool ok = linear_diophantine_equation(a, b, gcd(a, b), x_0, y_0, g); assert(ok); cout << x_0 << " " << y_0 << '\n'; return 0; } // Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=ja #endif