結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー codershifth
提出日時 2015-08-22 00:21:55
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 4,026 bytes
コンパイル時間 910 ms
コンパイル使用メモリ 117,248 KB
実行使用メモリ 13,888 KB
最終ジャッジ日時 2024-06-12 02:43:15
合計ジャッジ時間 7,664 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio;
import std.string;
import std.array;
import std.typecons;
import std.typetuple;
import std.container;
import std.algorithm;
import std.conv;
import std.math;
import std.format;

alias TypeTuple tie;

void readlnToken(T...)(auto ref T args)
{
    import std.stdio;
    import std.conv;
    import std.string;
    import std.array;

    auto line = split(readln().strip);
    foreach(ref arg; args)
    {
        arg = to!(typeof(arg))(line[0]);
        line = line[1..$];
    }
    assert(line.empty()); // got all token??
}

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

T gcd(T)(T a, T b)
{
    if (a < 0) a *= -1;
    if (b < 0) b *= -1;
    if ( a < b )
        swap(a,b);
    if ( b == 0 )
        return a;
    return gcd(b, a%b);
}

void solve()
{
    int Q;
    readlnToken(Q);

    foreach(i; 0..Q)
    {
        // 弾丸が反射するたびに Mami の位置が壁の向こう側に反転すると考えると
        // 弾丸はまっすぐ飛ぶと考えられる
        //             M              |  M
        //              \             | /
        // -----+      --\-+       ---+----
        //    /\|         \|          /
        //   M /|  =>     /|  ->     /|
        //    / |        / |        / |
        //
        int W,H,D,Mx,My,Hx,Hy,Vx,Vy;
        readlnToken(W,H,D,Mx,My,Hx,Hy,Vx,Vy);

        // 弾丸の発射方向を正方向に変換
        if (Vy < 0)
        {
            My = H - My;
            Hy = H - Hy;
            Vy = -Vy;
        }
        if (Vx < 0)
        {
            Mx = W - Mx;
            Hx = W - Hx;
            Vx = -Vx;
        }

        // 弾丸が水平・垂直に打たれるときは簡単に計算できる
        if (Vx == 0)
        {
            if ( Hx == Mx && ( (My > Hy && My-Hy <= D*Vy) || (My < Hy && 2*(H-Hy)+Hy-My <= D*Vy) ) )
                writeln("Hit");
            else
                writeln("Miss");
            continue;
        }
        if (Vy == 0)
        {
            if ( Hy == My && ( (Mx > Hx && Mx-Hx <= D*Vx) || (Mx < Hx && 2*(W-Hx)+Hx-Mx <= D*Vx) ) )
                writeln("Hit");
            else
                writeln("Miss");
            continue;
        }

        auto g = gcd(Vx,Vy);
        // Vx,Vy を互いに素にして D を最小公倍数倍しておく
        D *= g;
        Vx /= g;
        Vy /= g;

        // あたり判定関数
        bool hit(int tx, int ty)
        {
            import std.bigint;
            //
            // tx = T*Vx + Hx (mod 2*W)
            // ty = T*Vy + Hy (mod 2*H)
            //
            // なるような 0 < T < D が見つかればよい
            //
            // tx-Hx-T*Vx=2*W*n
            // ty-Hy-T*Vy=2*H*m
            //
            // (2*W)*n-(2*H)*m = Vy*(tx-Hx)-Vx*(ty-Hy)
            //   a       b           c
            // この不定方程式の解 (n,m) をもとめて T を計算する。
            //
            //
            BigInt a = 2*W*Vy;
            BigInt b = 2*H*Vx;
            BigInt c = Vy*(tx-Hx)-Vx*(ty-Hy);

            // a*n+(-b)*m = c
            auto g = gcd(a,-b);
            // 不定方程式が解をもたないケース
            if (c % g != 0)
                return false;
            a /= g;
            b /= g;
            c /= g;

            BigInt x,y;
            // a*n+(-b)*m = c をとく
            // まず a*x+(-b)*y = 1 なる (x,y) を求めて c 倍すればよい
            if (extgcd(a,-b,x,y) != 1)
                return false;
            x *= c;
            y *= c;
            auto T = (tx-Hx+2*W*x)/Vx;
            while (T < 0)
                T += 2*W/Vx;
            return T <= D;
        }

        if ( hit(Mx,My) || hit(2*W-Mx,My) || hit(Mx,2*H-My) || hit(2*W-Mx,2*H-My) )
            writeln("Hit");
        else
            writeln("Miss");
    }
}

void main()
{
    solve();
}
0