結果

問題 No.61 リベリオン
ユーザー krotonkroton
提出日時 2014-11-07 03:16:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 37 ms / 5,000 ms
コード長 2,570 bytes
コンパイル時間 670 ms
コンパイル使用メモリ 60,020 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-21 17:16:23
合計ジャッジ時間 1,388 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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);
    }
}

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 min_m = min_k(2 * H, ys - Hy - 1);
    
    ll k = max(
        min_k(b, c * alpha - min_n),
        min_k(a, -c * beta - min_m)
    );
    
    ll n = b * k + c * alpha;
    ll m = a * k - c * beta;
   
    ll x = 2 * W * n + xs;
    ll y = 2 * H * m + ys;
    
    ll num = (x - Hx) * (x - Hx) + (y - Hy) * (y - Hy);
    ll den = Vx * Vx + Vy * Vy;
    ll d2 = D * D;
    
    return num <= den * d2;
}

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