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= 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"