結果

問題 No.61 リベリオン
コンテスト
ユーザー kroton
提出日時 2014-11-11 05:58:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 2,776 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 60,768 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 16:13:55
合計ジャッジ時間 923 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b){
    if(b == 0)return a;
    return gcd(b, a % b);
}

ll extgcd(ll a, ll b, ll &x, ll &y){
    ll d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

ll min_k(ll a, ll c){
    if(c < 0){
        return (-c + a - 1) / a;
    } else {
        return -(c / a);
    }
}

ll max_k(ll a, ll c){
    if(c < 0){
        return (-c / a);
    } else {
        return -(c + a - 1) / a;
    }
}

ll mod_mul(ll a, ll b, ll m){
    a = (a % m + m) % m;
    b = (b % m + m) % m;
    
    ll res = 0;
    for(;b;b>>=1){
        if(b & 1){
            res = (res + a) % m;
        }
        a = (a + a) % m;
    }
    return res;
}

bool collision_check(ll W, ll H, ll D, ll Hx, ll Hy, ll Vx, ll Vy, ll xs, ll ys){
    ll a = 2 * W * Vy;
    ll b = 2 * H * Vx;
    ll c = Vx * (ys - Hy) - Vy * (xs - Hx);
    
    ll g = gcd(a, b);
    if(c % g != 0){
        return false;
    }
    
    a /= g;
    b /= g;
    c /= g;
    
    ll alpha, beta;
    extgcd(a, b, alpha, beta);
    
    ll min_n = min_k(2 * W, xs - Hx - 1);
    ll max_n = max_k(2 * W, xs - Hx - Vx * D);
    if(min_n > max_n)return false;
    
    ll C = mod_mul(c, alpha, b);
    if(C > max_n)return false;
    
    ll k = (max_n - C) / b;
    if(b * k + C < min_n)return false;
    
    return true;
}

bool line_check(ll W, ll D, ll Mx, ll Hx, ll Vx){
    ll dist;
    if(Mx > Hx){
        dist = Mx - Hx;
    } else {
        dist = (W - Hx) * 2 + Hx - Mx;
    }
    return dist <= Vx * D;
}

bool check(ll W, ll H, ll D, ll Mx, ll My, ll Hx, ll Hy, ll Vx, ll Vy){
    if(Vx < 0)return check(W, H, D, W - Mx, My, W - Hx, Hy, -Vx, Vy);
    if(Vy < 0)return check(W, H, D, Mx, H - My, Hx, H - Hy, Vx, -Vy);
    
    if(Vx == 0)return (Mx == Hx) && line_check(H, D, My, Hy, Vy);
    if(Vy == 0)return (My == Hy) && line_check(W, D, Mx, Hx, Vx);
    
    bool res = false;
    res |= collision_check(W, H, D, Hx, Hy, Vx, Vy, Mx, My);
    res |= collision_check(W, H, D, Hx, Hy, Vx, Vy, Mx + (W - Mx) * 2, My);
    res |= collision_check(W, H, D, Hx, Hy, Vx, Vy, Mx, My + (H - My) * 2);
    res |= collision_check(W, H, D, Hx, Hy, Vx, Vy, Mx + (W - Mx) * 2, My + (H - My) * 2);
    
    return res;
}

int main(){
    ll Q, W, H, D, Mx, My, Hx, Hy, Vx, Vy;
    
    cin >> Q;
    for(int i=0;i<Q;i++){
        cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
        
        bool res = check(W, H, D, Mx, My, Hx, Hy, Vx, Vy);
        cout << (res ? "Hit" : "Miss") << endl;
    }
    
    return 0;
}
0