結果

問題 No.62 リベリオン(Extra)
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-23 23:58:58
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 2,774 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 7,068 KB
実行使用メモリ 13,596 KB
最終ジャッジ日時 2024-06-23 22:22:21
合計ジャッジ時間 7,182 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def gcd(a,b):
    if b<a:
        return gcd(b,a)
    if b%a==0:
        return a
    return gcd(b%a,a)

def ext_gcd(a,b):
    # return (n,m) s.t. na+mb=1
    if b<a:
        (N,M)=ext_gcd(b,a)
        return (M,N)
    if a==1:
        return (b-1,0)
    r=b%a
    t=b/a
    # at+r=b, so na+mb=1=na+(at+r)m=(n+tm)a+mr
    (N,M)=ext_gcd(r,a)
    # N=m, M=n+tm so n=M-tN, m=N
    return (M-N*t,N)


Q=int(raw_input())
for i in range(Q):
    W,H,D,Mx,My,Hx,Hy,Vx,Vy=map(int,raw_input().split())
    Vg=max(abs(Vx),abs(Vy))
    if Vx == 0:
        if Mx==Hx and ((My-Hy)<=D*Vy or (My<Hy and My+Hy<=D*abs(Vy)) or (My>Hy and 2*H-My-Hy <= D*abs(Vy)) ):
            print "Hit"
        else:
            print "Miss"
        continue
    if Vy == 0:
        if My==Hy and ((Mx-Hx)<=D*Vx or (Mx<Hx and Mx+Hx<=D*abs(Vx)) or (Mx>Hx and 2*W-Mx-Hx <= D*abs(Vx)) ):
            print "Hit"
        else:
            print "Miss"
        continue
    Vg=gcd(abs(Vx),abs(Vy))
    Vx/=Vg
    Vy/=Vg
    D*=Vg
    if Vx < 0:
        Vx=-Vx
        Mx=W-Mx
        Hx=W-Hx
    if Vy < 0:
        Vy=-Vy
        My=H-My
        Hy=H-Hy
    ## find k s.t. Hx+kVx= 2mW+Mx and Hy+kVy = 2nH+My
    ##             (Hx-Mx)Vy-(Hy-My)Vx = m(2WVy)-n(2HVx)
    ## find k s.t. Hx+kVx= 2mW-Mx and Hy+kVy = 2nH-My...
    conlist=[(Hx-My)*Vy-(Hy-My)*Vx, (Hx+My)*Vy-(Hy-My)*Vx, (Hx-My)*Vy-(Hy+My)*Vx,(Hx+My)*Vy-(Hy+My)*Vx]
    isHit = False
    for con in conlist:
        if con==0:
            continue
        #print con
        g=gcd(abs(2*W*Vy),abs(2*H*Vx))
        n,m=ext_gcd(abs(2*W*Vy/g),abs(2*H*Vx/g))
        ## 1 = n*2WVy/g+m*2HVx/g
        #print 1,"=",n,"*|2*",W,"*",Vy,"/",g,"|", "+", m,"*|2*",H,"*",Vx,"/",g,"|"
        if con%g != 0:
            continue
        n*=con/g
        m*=con/g
        ## con=(Hx-Mx)Vy-(Hy-My)Vx = n*2WVy+m*2HVx = n*(2WVy/g)*g + m*(2HVx/g)*g
        ## not only (n,m) but also (n+t(2HVx/g), m-t(2WVy/g)) is possible
        ## k = (2mW+Mx-Hx)/Vx <=D is requird. k>0 of course
        ## let's find out t argmin_t( (2W(m-t(2WVx/g))+Mx-Hx)/Vx >0 )
        ## note that we can assume Vx>0 from previous code
        ## 2W(m-t(2WVx/g))   > Hx-Mx
        while (2*m*W+Mx-Hx) <= 0:
            m+=(2*W*Vy/g)
            n-=(2*H*Vx/g)
        while (2*m*W+Mx-Hx) > 0:
            #print con,"=",n,"*2",W,"*",Vy,"+",m,"*2",H,"*",Vx
            if (2*m*W+Mx-Hy) <= Vx*D:
                isHit=True
                #print con,"=",n,"*2",W,"*",Vy,"+",m,"*2",H,"*",Vx
                #print Hx,"+",(2*m*W+Mx-Hx)/Vx,"*",Vx, "=2*",m,"*",W,"+",Mx
                #print (2*m*W+Mx-Hx)/Vx,"<=", Vx ,"*",D
                break
            m-=(2*W*Vy/g)
            n+=(2*H*Vx/g)
        if isHit:
            break
    if isHit:
        print "Hit"
    else:
        print "Miss"
0