結果

問題 No.62 リベリオン(Extra)
ユーザー codershifth
提出日時 2015-08-22 10:29:19
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,232 ms / 5,000 ms
コード長 4,456 bytes
コンパイル時間 1,065 ms
コンパイル使用メモリ 132,276 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-12 02:44:14
合計ジャッジ時間 3,124 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

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;
    assert(a>=0 && b>=0);
    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)
{
    assert(a>=0 && b>=0);
    if ( a < b )
        swap(a,b);
    if ( b == 0 )
        return a;
    return gcd(b, a%b);
}
void solve()
{
    import std.bigint;
    int Q;
    readlnToken(Q);
    foreach(i; 0..Q)
    {
        // 弾丸が反射するたびに Mami の位置が壁の向こう側に反転すると考えると
        // 弾丸はまっすぐ飛ぶと考えられる
        //             M              |  M
        //              \             | /
        // -----+      --\-+       ---+----
        //    /\|         \|          /
        //   M /|  =>     /|  ->     /|
        //    / |        / |        / |
        //
        BigInt 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(BigInt tx, BigInt ty)
        {
            //
            // tx = T*Vx + Hx (mod 2*W)
            // ty = T*Vy + Hy (mod 2*H)
            //
            // なるような T <= D が見つかればよい
            //
            // tx-Hx-T*Vx=2*W*n
            // ty-Hy-T*Vy=2*H*m
            //
            // (2*W*Vy)*n-(2*H*Vx)*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 倍すればよい
            // 今 a,b を正として扱いたいから
            // a*x+(-b)*y = 1 の解 (x,-y) を使う
            if (extgcd(a,-b,x,y) != 1)
                return false;
            auto m = -y*c%a; // a の倍数分は n にゆずる
            auto T = (ty-Hy-2*H*m)/Vy;
            // a*(n+b)+b*(m-a) = c で gcd(a,b)=1 より
            // 2*H*a/Vy が周期になる
            auto period = 2*H*a/Vy;
            T %= period;
            // 必要なら period を加えれば正になる
            if (T < 0)
                T += period;
            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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1