#193685 (C++14) No.62 リベリオン(Extra)

• 問題: No.62 リベリオン(Extra)
• ユーザー: Pachicobue
• 提出日時: 2017-08-03 18:15:07
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,670 bytes
• コンパイル時間: 1,589 ms
• コンパイル使用メモリ: 169,288 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-11 20:30:38
• 合計ジャッジ時間: 2,114 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 2 WA * 1

ソースコード

// {{{ Templates
#include <bits/stdc++.h>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using bigint = __int128_t;
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 = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

// }}}

bigint absol(const bigint& a)
{
    return (a < 0) ? -a : a;
}

template <typename T>
T extgcd(const T a, const T b, T& x, T& y)  // ax+by=gcd(a,b)
{
    T d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    assert(a * x + b * y == d);
    return d;
}

struct FieldInfo {
    bigint W;
    bigint H;
    bigint D;
    bigint MX;
    bigint MY;
    bigint HX;
    bigint HY;
    bigint VX;
    bigint VY;
};

bool hit(const FieldInfo& f, const bool oddv, const bool oddh)
{
    const bigint W = f.W;
    const bigint H = f.H;
    const bigint D = f.D;
    const bigint MX = f.MX;
    const bigint MY = f.MY;
    const bigint HX = f.HX;
    const bigint HY = f.HY;
    const bigint VX = f.VX;
    const bigint VY = f.VY;

    if (VX == 0) {
        if (MX != HX) {
            return false;
        } else {
            const bigint dist = (VY > 0) ? ((HY <= MY) ? MY - HY : 2 * H - (MY + HY)) : ((HY >= MY) ? HY - MY : MY + HY);
            return dist <= absol(VY) * D;
        }

    } else if (VY == 0) {
        if (MY != HY) {
            return false;
        } else {
            const bigint dist = (VX > 0) ? ((HX <= MX) ? MX - HX : 2 * W - (MX + HX)) : ((HX >= MX) ? HX - MX : MX + HX);
            return dist <= absol(VX) * D;
        }
    }

    const bigint K = VY * HX - VX * HY + ((oddv) ? -VY * MX : VY * MX) + ((oddh) ? VX * MY : -VX * MY);
    const bigint A = 2 * VY * W;
    const bigint B = -2 * VX * H;
    bigint m, n;
    bigint g = extgcd(A, B, m, n);
    if (K % g != 0) {
        return false;
    }
    m *= K / g;
    n *= K / g;
    assert(A * m + B * n == K);

    bigint x = 2 * m * W - HX + ((oddv) ? MX : -MX);
    bigint y = 2 * n * H - HY + ((oddh) ? MY : -MY);
    const bigint deltax = absol(2 * H * W * VX / g);
    const bigint deltay = absol(2 * H * W * VY / g);
    x = ((x % deltax) + deltax) % deltax;
    y = ((y % deltay) + deltay) % deltay;
    return x <= D * absol(VX) and y <= D * absol(VY);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        FieldInfo f;
        ll w, h, d, mx, my, hx, hy, vx, vy;
        cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
        f.W = (bigint)(w);
        f.H = (bigint)(h);
        f.D = (bigint)(d);
        f.MX = (bigint)(mx);
        f.MY = (bigint)(my);
        f.HX = (bigint)(hx);
        f.HY = (bigint)(hy);
        f.VX = (bigint)(vx);
        f.VY = (bigint)(vy);

        bool hitflag = false;
        for (int i = 0; i < 4; i++) {
            const bool oddv = (bool)(i / 2);
            const bool oddh = (bool)(i % 2);
            if (hit(f, oddv, oddh)) {
                hitflag = true;
                break;
            }
        }
        if (hitflag) {
            cout << "Hit" << endl;
        } else {
            cout << "Miss" << endl;
        }
    }

    return 0;
}