結果

問題 No.62 リベリオン(Extra)
ユーザー 👑 kmjpkmjp
提出日時 2014-11-10 23:08:46
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,302 bytes
コンパイル時間 57 ms
コンパイル使用メモリ 6,676 KB
実行使用メモリ 7,820 KB
最終ジャッジ日時 2023-08-30 03:05:15
合計ジャッジ時間 1,334 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 22 ms
7,820 KB
testcase_01 AC 22 ms
7,728 KB
testcase_02 AC 126 ms
7,580 KB
testcase_03 AC 118 ms
7,668 KB
testcase_04 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import fractions

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

def ext_gcd(p,q):
	if q==0:
		return (p,1,0)
	(g,x,y) = ext_gcd(q, p%q)
	return (g,y,x - q//p*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=ext_gcd(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