結果
| 問題 |
No.62 リベリオン(Extra)
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-07-15 18:27:58 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,620 bytes |
| コンパイル時間 | 1,793 ms |
| コンパイル使用メモリ | 171,008 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-08 02:32:39 |
| 合計ジャッジ時間 | 2,494 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | WA * 3 |
ソースコード
#include <bits/stdc++.h>
#define show(x) cout << #x << " = " << x << endl
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz=" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
os << "(" << p.first << "," << p.second
<< ")";
return os;
}
constexpr ll MOD = 1e9 + 7;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;
inline pair<ll, ll> extgcd(const ll x, const ll y)
{
ll r0 = x;
ll r1 = y;
ll a0 = 1;
ll a1 = 0;
ll b0 = 0;
ll b1 = 1;
while (r1 > 0) {
const ll q1 = r0 / r1;
const ll r2 = r0 % r1;
const ll a2 = a0 - q1 * a1;
const ll b2 = b0 - q1 * b1;
r0 = r1;
r1 = r2;
a0 = a1;
a1 = a2;
b0 = b1;
b1 = b2;
}
return make_pair(a0 / r0, b0 / r0);
}
template <typename T>
T gcd(const T a, const T b)
{
return b ? gcd(b, a % b) : a;
}
template <typename T>
T lcm(const T a, const T b)
{
return (a / gcd(a, b)) * b;
}
int main()
{
ll Q;
cin >> Q;
for (ll query = 0; query < Q; query++) {
ll w, h, d, mx, my, hx, hy, vx, vy;
cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
if (vx != 0 and vy != 0) {
const ll g = gcd(vx, vy);
d *= g;
vx /= g;
vy /= g;
const ll gx = gcd(2 * w, vx);
const ll gy = gcd(2 * h, vy);
const ll x[2] = {hx - mx, hx + mx - 2 * w};
const ll y[2] = {hy - my, hy + my - 2 * h};
const ll W = 2 * w / gx;
const ll H = 2 * h / gy;
const ll VX = vx / gx;
const ll VY = vy / gy;
bool ok = false;
for (int i = 0; i < 4; i++) {
ll X = x[i % 2];
ll Y = y[i / 2];
if (X % gx != 0) {
continue;
}
X /= gx;
if (Y % gy != 0) {
continue;
}
Y /= gy;
// W*k-VX*t = X
// H*l-VY*t = Y
const pair<ll, ll> px = extgcd(W, VX);
const pair<ll, ll> py = extgcd(H, VY);
const ll k0 = px.first * X;
const ll t0 = -px.second * X;
const ll l0 = py.first * Y;
const ll t1 = -py.second * Y;
// show(W * k0 - VX * t0 - X);
// show(H * l0 - VY * t1 - Y);
// W_*i_-j_*H_ = delta_t
const ll g_ = gcd(W, H);
ll delta_t = t1 - t0;
if (delta_t % g_ != 0) {
continue;
}
const ll W_ = W / g_;
const ll H_ = H / g_;
delta_t /= g_;
const pair<ll, ll> pt = extgcd(W_, H_);
const ll i_ = pt.first * delta_t;
const ll j_ = -pt.second * delta_t;
// show(W_ * i_ - j_ * H_ - delta_t);
ll k = k0 + i_ * VX;
ll l = l0 + (i_ * W_ - delta_t) / H_ * VY;
ll t = t0 + i_ * W;
// show(d);
// show(k);
// show(l);
// show(t);
const ll dk = H_ * VX;
const ll dl = W_ * VY;
const ll dt = H_ * W;
// show(dk);
// show(dl);
// show(dt);
ll minimum = -INF<ll>;
ll maximum = INF<ll>;
if (dk > 0) {
ll kmin = (-k) / dk;
if (dk * kmin < -k) {
kmin++;
}
minimum = max(minimum, kmin);
} else if (dk < 0) {
ll kmax = (-k) / dk;
if (dk * kmax > -k) {
kmax--;
}
maximum = min(maximum, kmax);
}
if (dl > 0) {
ll lmin = (-l) / dl;
if (dl * lmin < -l) {
lmin++;
}
minimum = max(minimum, lmin);
} else if (dl < 0) {
ll lmax = (-l) / dl;
if (dl * lmax > -l) {
lmax--;
}
maximum = min(maximum, lmax);
}
if (dt > 0) {
ll tmin = (-t) / dt;
if (tmin * dt < -t) {
tmin++;
}
ll tmax = (d - t) / dt;
if (tmax * dt > (d - t)) {
tmax--;
}
minimum = max(minimum, tmin);
maximum = min(maximum, tmax);
} else if (dt < 0) {
ll tmin = (d - t) / dt;
if (tmin * dt < d - t) {
tmin++;
}
ll tmax = (-t) / dt;
if (tmax * dt > (-t)) {
tmax--;
}
minimum = max(minimum, tmin);
maximum = min(maximum, tmax);
}
// show(maximum);
// show(minimum);
if (maximum >= minimum) {
// show(k + dk * minimum);
// show(l + dl * minimum);
// show(t + dt * minimum);
ok = true;
break;
}
}
if (ok) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
} else if (vx == 0) {
if (hx != mx) {
cout << "Miss" << endl;
} else {
if (vy > 0) {
if (my - hy > 0) {
if (my - hy <= d * vy) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
} else {
if (2 * h - my - hy <= d * vy) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
}
} else {
vy *= -1;
if (my - hy > 0) {
if (2 * h - hy - my <= d * vy) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
} else {
if (hy + my <= d * vy) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
}
}
}
} else {
if (hy != my) {
cout << "Miss" << endl;
} else {
if (vx > 0) {
if (mx - hx > 0) {
if (mx - hx <= d * vx) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
} else {
if (2 * w - mx - hx <= d * vx) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
}
} else {
vx *= -1;
if (mx - hx > 0) {
if (2 * w - hx - mx <= d * vx) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
} else {
if (hx + mx <= d * vx) {
cout << "Hit" << endl;
} else {
cout << "Miss" << endl;
}
}
}
}
}
}
return 0;
}