import math def gcd(a,b): if bHy 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 (MxHx 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))) 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"