結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー なお
提出日時 2014-11-12 20:11:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 93 ms / 5,000 ms
コード長 2,379 bytes
コンパイル時間 1,371 ms
コンパイル使用メモリ 161,500 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-31 10:02:06
合計ジャッジ時間 2,248 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))

ll gcd(ll n, ll m){return m?gcd(m,n%m):n;}
ll extgcd(ll a,ll b,ll &m,ll &n){ll g=a;m=1;n=0;if(b)g=extgcd(b,a%b,n,m),n-=(a/b)*m;return g;}

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

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

bool colcheck(ll W,ll H,ll D,ll Mx,ll My,ll Hx,ll Hy,ll Vx,ll Vy){
    ll a = W * 2 * Vy;
    ll b = H * 2 * Vx;
    ll c = Vx * (My - Hy) - Vy * (Mx - 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(W * 2, Mx - Hx - 1);
    ll max_n = max_k(W * 2, Mx - Hx - Vx * D);
    if(min_n > max_n) return false;

    // n - c'α ≡ 0(mod b') → n ≡ c'α (mod b')
    ll C = mulmod(c, alpha, b); // C = (c'*α) % b'
    if(C > max_n) return false;

    // n - c'α = b'k
    ll k = (max_n - C) / b;

    // n = b'k + c'α
    if(b * k + C < min_n) return false;

    return true;
}

bool linecheck(ll S,ll D,ll M,ll H,ll V){
    if(H < M) return (M-H <= V*D);  // 直接
    return ( S*2-H-M <= V*D );      // 1回壁反射
}

bool solve(ll W,ll H,ll D,ll Mx,ll My,ll Hx,ll Hy,ll Vx,ll 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(Hx != Mx) return false;
        return linecheck(H,D,My,Hy,Vy);
    }
    if(Vy == 0){
        if(Hy != My) return false;
        return linecheck(W,D,Mx,Hx,Vx);
    }

    if(colcheck(W,H,D,Mx    ,My    ,Hx,Hy,Vx,Vy)) return 1;
    if(colcheck(W,H,D,W*2-Mx,My    ,Hx,Hy,Vx,Vy)) return 1;
    if(colcheck(W,H,D,Mx    ,H*2-My,Hx,Hy,Vx,Vy)) return 1;
    if(colcheck(W,H,D,W*2-Mx,H*2-My,Hx,Hy,Vx,Vy)) return 1;
    return false;
}

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