結果

問題 No.62 リベリオン(Extra)
ユーザー kmjpkmjp
提出日時 2014-11-10 23:01:49
言語 Python2
(2.7.18)
結果
AC  
実行時間 301 ms / 5,000 ms
コード長 1,337 bytes
コンパイル時間 537 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-06-10 02:21:39
合計ジャッジ時間 1,799 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,064 KB
testcase_01 AC 20 ms
8,192 KB
testcase_02 AC 110 ms
8,064 KB
testcase_03 AC 110 ms
8,064 KB
testcase_04 AC 301 ms
8,192 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import fractions

W=H=D=MX=MY=HX=HY=VX=VY=0

def ext_gcd(p,q):
	print (p,q)
	if q==0:
		return (p,1,0)
	(g,y,x) = ext_gcd(q, p%q)
	print (p,q,g,y,x)
	x -= p/q%y
	return (g,x,y)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def calc(tx,ty):
	A = 2*W*VY
	B = -2*H*VX
	C = ty*VX-tx*VY+HX*VY-HY*VX
	
	g = fractions.gcd(A, -B)
	if C % g > 0:
		return False
	A /= g
	B /= g
	C /= g
	
	g,x,y=egcd(A,B);
	
	m = C*y%A
	tv=(ty+2*H*m-HY)/VY;
	
	tv %= 2*H*A/VY;
	if tv<0:
		tv += 2*H*A/VY;
	return tv<=D

Q = input()
while Q > 0:
	Q -= 1
	W,H,D,MX,MY,HX,HY,VX,VY=map(int,raw_input().strip().split())
	
	if VX < 0:
		MX = W - MX
		HX = W - HX
		VX = -VX
	if VY < 0:
		MY = H - MY
		HY = H - HY
		VY = -VY
	
	if VX == 0:
		if MX==HX and ((MY>HY and (MY-HY)<=D*VY) or (MY<HY and (2*H-MY-HY)<=D*VY)):
			print "Hit"
		else:
			print "Miss"
		continue
	
	if VY == 0:
		if MY==HY and ((MX>HX and (MX-HX)<=D*VX) or (MX<HX and (2*W-MX-HX)<=D*VX)):
			print "Hit"
		else:
			print "Miss"
		continue
	
	g = fractions.gcd(VX, VY)
	D *= g
	VX /= g
	VY /= g
	
	if calc(MX,MY) or calc(2*W-MX,MY) or calc(MX,2*H-MY) or calc(2*W-MX,2*H-MY):
		print "Hit"
	else:
		print "Miss"
0