結果

問題 No.62 リベリオン(Extra)
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-25 00:57:02
言語 Python2
(2.7.18)
結果
AC  
実行時間 654 ms / 5,000 ms
コード長 2,967 bytes
コンパイル時間 128 ms
コンパイル使用メモリ 7,168 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 23:07:35
合計ジャッジ時間 1,579 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
6,816 KB
testcase_01 AC 10 ms
6,940 KB
testcase_02 AC 162 ms
6,940 KB
testcase_03 AC 161 ms
6,940 KB
testcase_04 AC 654 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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 (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= 2nW+Mx and Hy+kVy = 2mH+My
    ##             (Hx-Mx)Vy-(Hy-My)Vx = n(2WVy)-m(2HVx)
    ## find k s.t. Hx+kVx= 2mW-Mx and Hy+kVy = 2nH-My...
    #conlist=[(Hx-Mx)*Vy-(Hy-My)*Vx, (Hx+Mx)*Vy-(Hy-My)*Vx, (Hx-Mx)*Vy-(Hy+My)*Vx,(Hx+Mx)*Vy-(Hy+My)*Vx]
    
    conList=[(Hx,Mx,Hy,My),(Hx,-Mx,Hy,My),(Hx,Mx,Hy,-My),(Hx,-Mx,Hy,-My)]
    isHit = False
    for (hx,mx,hy,my) in conList:
        #print hx,mx,hy,my,Vx,Vy
        con=(hx-mx)*Vy-(hy-my)*Vx
        #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 = (2nW+Mx-Hx)/Vx <=D is requird. k>0 of course
        ## let's find out t argmin_t( 2(n+t(2HVx/g))W+Mx-Hx >0 )
        ## n+t(2HVx/g) > (-Mx+Hx)/2W
        ## t(2HVx/g)>(Hx-Mx)/2W - n
        #print con,"=",n,"*2",W,"*",Vy,"+",m,"*2",H,"*",Vx
        #t=int(math.ceil(((hx-mx)/(2.0*W)-n)/(2*H*Vx/g))) #this might cause error
        t= ((hx-mx)-n*2*W+(2*W*2*H*Vx/g)-1)/(2*W*2*H*Vx/g)
        n+=t*(2*H*Vx/g)
        m-=t*(2*W*Vy/g)
        #print con,"=",n,"*2",W,"*",Vy,"+",m,"*2",H,"*",Vx
        #print 2,"*",n,"*",H,"+",my,"-",hy,"=",2*n*H+my-hy,"...",  2*H*Vx/g, "vs" , Vy,"*",D
        if (2*n*W+mx-hx) <= Vx*D:
            isHit=True
            #print con,"=",n,"*2",W,"*",Vy,"+",m,"*2",H,"*",Vx
            #print Hx,"+",(2*n*W+mx-hx)/Vx,"*",Vx, "=2*",n,"*",W,"+",mx
            #print (2*n*W+mx-hx)/Vx,"<=", Vx ,"*",D
            break
    if isHit:
        print "Hit"
    else:
        print "Miss"
0