結果

問題 No.62 リベリオン(Extra)
ユーザー t98slidert98slider
提出日時 2022-05-17 12:08:47
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,648 bytes
コンパイル時間 5,750 ms
コンパイル使用メモリ 401,432 KB
実行使用メモリ 4,356 KB
最終ジャッジ日時 2023-10-13 09:15:18
合計ジャッジ時間 6,624 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,352 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

tuple<int1024_t,int1024_t,int1024_t> ext_gcd(int1024_t p, int1024_t q){
    if(q == 0)return make_tuple(p, 1, 0);
    int1024_t g, x, y;
    tie(g, y, x) = ext_gcd(q, p % q);
    return make_tuple(g, x, y - (p / q) * x);
}

int1024_t igcd(int1024_t a, int1024_t b){
    return b == 0 ? a : igcd(b, a % b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int1024_t W, H, D, Mx, My, Hx, Hy, Vx, Vy;
    auto solve = [&](int1024_t Vx, int1024_t Vy, int1024_t Sx, int1024_t Sy, int1024_t Dx, int1024_t Dy){
        int1024_t x, y, g, A, B, C, D, XX, YY, Bx, By;
        int1024_t gg, gg1, gg2;
        g = igcd(Vx, Vy);
        Vx /= g, Vy /= g;
        Sx %= Dx;
        Sy %= Dy;
        if(Sx < 0)Sx += Dx;
        if(Sy < 0)Sy += Dy;
        A = Dx * Vy, B = Dy * Vx, C = Vx * Sy - Vy * Sx;
        g = igcd(A, B);
        if(C % g != 0)return false;
        A /= g, B /= g, C /= g;
        tie(g, x, y) = ext_gcd(A, B);
        Bx = C * x, By = -C * y;
        gg1 = Bx / B, gg2 = By / A;
        gg = gg1 < gg2 ? gg1 : gg2;
        Bx -= gg * B, By -= gg * A;
        while(Bx >= B && By >= A)Bx -= B, By -= A;
        while(Bx < 0 || By < 0)Bx += B, By += A;
        x = Sx + Bx * Dx;
        y = Sy + By * Dy;
        return (x <= Vx && y <= Vy);
    };
    int t;
    cin >> t;
    while(t--){
        cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
        if(Vx < 0){
            Mx = W - Mx, Hx = W - Hx, Vx = -Vx;
        }
        if(Vy < 0){
            My = H - My, Hy = H - Hy, Vy = -Vy;
        }
        if(Vx == 0){
            if((Mx == Hx) && ((My >= Hy && My - Hy <= D * Vy) || (My < Hy && 2 * H - My - Hy <= D * Vy))){
                cout << "Hit" << '\n';
            }else{
                cout << "Miss" << '\n';
            }
            continue;
        }
        if(Vy == 0){
            if((My == Hy) && ((Mx >= Hx && Mx - Hx <= D * Vx) || (Mx < Hx && 2 * W - Mx - Hx <= D * Vx))){
                cout << "Hit" << '\n';
            }else{
                cout << "Miss" << '\n';
            }
            continue;
        }
        int1024_t Rx = 2 * W - Mx, Ry = 2 * H - My;
        if(solve(Vx * D, Vy * D, Mx - Hx, My - Hy, 2 * W, 2 * H) ||
           solve(Vx * D, Vy * D, Rx - Hx, My - Hy, 2 * W, 2 * H) ||
           solve(Vx * D, Vy * D, Mx - Hx, Ry - Hy, 2 * W, 2 * H) ||
           solve(Vx * D, Vy * D, Rx - Hx, Ry - Hy, 2 * W, 2 * H)){
               cout << "Hit" << '\n';
        }else{
            cout << "Miss" << '\n';
        }
    }
}
0