Problem:


UFO 撃墜作戦

  40XX 年、地球は宇宙人の侵攻を受けていた!すでに地球のほとんどは宇宙人により制圧されており、残る防衛拠点は鶴ヶ城要塞のみになってしまった。その鶴ヶ城要塞にも、制圧部隊が次々に迫ってきている。

  

  しかし、希望は残されている。防衛軍の最終兵器、超長距離貫通レーザー砲が完成したのだ。欠点といえば、   威力が出るまでに一定の距離が必要で、          近すぎる敵はただ通りぬけてしまうということだ。  威力が出ない範囲に侵入した敵は、他の戦力でどうにかするしかない。防衛軍の参謀は、侵入して来た UFO に対処するために、その数を知らなければならないのだが、あまりにも敵が多いせいでうまく数えられそうにない。そこで参謀はあなたに、レーザーに撃墜されなかった UFO の数を出力するプログラムを用意するように命令した。戦闘開始までにプログラムを作成し、鶴ヶ城要塞を守る力となろう。

  敵の UFO はただまっすぐにレーザー砲のある拠点を目指して突撃してくる(UFO には互いにすり抜ける処理が施されており、衝突してしまうことはない) 。レーザー砲は、初期状態から 1 分後に最も近い UFO の中心を狙ってレーザーを発射し始め、それから 1 分ごとに同じ条件でレーザーを発射し続ける。レーザーは貫通し、その先にある UFO もレーザーがかすっただけで撃墜することができる。しかし、このレーザーには威力の出ない範囲があり、その範囲に入ってしまったUFO は狙っても意味がないため、狙わないように設計されている。撃墜できるだけ撃墜したとき、レーザーの威力が出ない範囲には何機の UFO が侵入しただろうか。

  レーザーの威力が出ない範囲の半径 R と、襲来する UFO の情報を入力とし、撃墜されず侵入している UFO が何機いるかを出力するプログラムを作成してください。 襲来する UFO の情報は、UFO の数 N 、各 UFO の初期座標 (x0, y0)、各 UFO の半径 r 、各 UFO の分速 v で構成されます。

  座標の原点 (0 , 0) をレーザー砲の位置とします。レーザー砲と UFO の距離は原点から UFO の中心までの距離で与えられ、この距離が R 以下の UFO はレーザーの威力が出ない範囲に入ったとします。狙うべき対象が同時に複数存在する場合はないものとして考えます。計算は全て平面上で考え、入力はすべて整数で与えられます。

Input

複数のデータセットの並びが入力として与えられます。 入力の終わりはゼロふたつの行で示されます。
各データセットは以下の形式で与えられます。

R N
x01 y01 r1 v1
x02 y02 r2 v2
:
x0N y0N rN vN

1 行目にレーザーの威力が出ない範囲の半径 R (1 ≤ R ≤ 500) とUFO の数 N (1 ≤ N ≤ 100) が与えられます。続く N 行に i 機目の UFO の情報 x0i, y0i (-100 ≤ x0i, y0i ≤ 1000), ri,  vi (1 ≤ ri, vi ≤ 500) が与えられます。

データセットの数は 50 を超えません。

Output

入力データセットごとに、レーザーの威力が出ない範囲に侵入した UFO の数を1行に出力します。

Sample Input

100 5
101 101 5 5
110 110 2 3
-112 -100 9 11
-208 160 82 90
-110 108 10 2
10 11
15 0 5 1
25 0 5 1
35 0 5 1
45 0 5 1
55 0 5 1
65 0 5 1
75 0 5 1
85 0 5 1
95 0 5 1
-20 0 5 20
-30 0 500 5
0 0

Output for the Sample Input

1
1



Sample input:
100 5
101 101 5 5
110 110 2 3
-112 -100 9 11
-208 160 82 90
-110 108 10 2
10 11
15 0 5 1
25 0 5 1
35 0 5 1
45 0 5 1
55 0 5 1
65 0 5 1
75 0 5 1
85 0 5 1
95 0 5 1
-20 0 5 20
-30 0 500 5
0 0


Sample output:
1
1

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	D=abs(a*ufo[0]+b*ufo[1])/math.sqrt(a**2+b**2)
	return True if D<=ufo[2] else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d,cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i].append(ufos[i][0]/ufos[i][4])
		ufos[i].append(ufos[i][1]/ufos[i][4])
	#ufos[i]=[x,y,r,v,d,cos,sin]
	invade=0
	while ufos:
		# update d,x,y
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
			ufos[i][0]=ufos[i][4]*ufos[i][5]
			ufos[i][1]=ufos[i][4]*ufos[i][6]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R:
				invade+=1
				ufos.pop(i)
		if len(ufos)==0:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				ufos.pop(i)
				
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	D=abs(a*ufo[0]+b*ufo[1])/math.sqrt(a**2+b**2)
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d,cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i].append(ufos[i][0]/ufos[i][4])
		ufos[i].append(ufos[i][1]/ufos[i][4])
	#ufos[i]=[x,y,r,v,d,cos,sin]
	invade=0
	while ufos:
		# update d,x,y
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
			ufos[i][0]=ufos[i][4]*ufos[i][5]
			ufos[i][1]=ufos[i][4]*ufos[i][6]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
				
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	D=abs(a*ufo[0]+b*ufo[1])/math.sqrt(a**2+b**2)
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d,cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i].append(ufos[i][0]/ufos[i][4])
		ufos[i].append(ufos[i][1]/ufos[i][4])
	#ufos[i]=[x,y,r,v,d,cos,sin]
	invade=0
	while ufos:
		# update d,x,y
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
			ufos[i][0]-=ufos[i][3]*ufos[i][5]
			ufos[i][1]-=ufos[i][3]*ufos[i][6]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
				
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	D=abs(a*ufo[0]+b*ufo[1])/math.sqrt(a**2+b**2)
	return True if D<=ufo[2]+1e-5 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d,cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i].append(ufos[i][0]/ufos[i][4])
		ufos[i].append(ufos[i][1]/ufos[i][4])
	#ufos[i]=[x,y,r,v,d,cos,sin]
	invade=0
	while ufos:
		# update d,x,y
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
			ufos[i][0]-=ufos[i][3]*ufos[i][5]
			ufos[i][1]-=ufos[i][3]*ufos[i][6]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
				
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-5 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
				
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[0]<0 or -b*ufo[1]<0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[0]<0 or b*ufo[1]<0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[0]<0 and -b*ufo[1]<0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[1]<0 and -b*ufo[0]<0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[1]<=0 and -b*ufo[0]<=0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		#a=sin, b=-cos 
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[1]<=0 and -b*ufo[0]<=0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	if math.sqrt(ufo[4]**2-D**2)<=R:return False
	return True if D<=ufo[2]+1e-7 else False

while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		#a=sin, b=-cos 
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[1]<=0 and -b*ufo[0]<=0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	if D>ufo[2]:
		return False
	else:
		if math.sqrt(ufo[4]**2-D**2)+math.sqrt(ufo[2]**2-D**2)<=R:
			return False
		else:
			return True
			
while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(int,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		#a=sin, b=-cos 
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Wrong Answer

Solution code:
import math
def isHit(a,b,ufo):
	if a*ufo[1]<=0 and -b*ufo[0]<=0:return False
	D=abs(a*ufo[0]+b*ufo[1])*ufo[4]
	if D>ufo[2]:
		return False
	else:
		if math.sqrt(ufo[4]**2-D**2)+math.sqrt(ufo[2]**2-D**2)<=R:
			return False
		else:
			return True
			
while 1:
	R,N=map(int,raw_input().split())
	if R==0:break
	ufos=[map(float,raw_input().split()) for i in range(N)]
	for i in range(N):
		#append d and calc cos,sin
		ufos[i].append(math.sqrt(ufos[i][0]**2+ufos[i][1]**2))
		ufos[i][0]/=ufos[i][4]
		ufos[i][1]/=ufos[i][4]
	#ufos[i]=[cos,sin,r,v,d]
	invade=0
	while ufos:
		# update d
		for i in range(len(ufos)):
			ufos[i][4]-=ufos[i][3]
		# remove ufo d<=R
		for i in range(len(ufos)-1,-1,-1):
			if ufos[i][4]<=R+1e-7:
				invade+=1
				del ufos[i]
		if len(ufos)<=1:break
		# remove nearest ufo
		ufos=sorted(ufos,key=lambda i:i[4])
		target=ufos.pop(0)
		#a=sin, b=-cos 
		a,b=target[1],-target[0]
		# remove ufo that laser hits
		for i in range(len(ufos)-1,-1,-1):
			if isHit(a,b,ufos[i]):
				del ufos[i]
	print invade

Submission status: Accepted

Solution code:
import math
ans = []
while True:
    ufo = []
    n = raw_input().split()
    if n == ["0", "0"]:
        for an in ans:
            print an
        break
    else:
        R = int(n[0])
        for i in range(int(n[1])):
            m = [int(f) for f in raw_input().split()]
            ufo.append([math.sqrt(m[0] ** 2 + m[1] ** 2), math.sqrt(m[0] ** 2 + m[1] ** 2), (m[0], m[1]), m[2], m[3]])
        a = 0
        while len(ufo) > 0:
            flag = True
            for xs in ufo: xs[0] -= xs[4]
            ufo.sort()
            for xs in ufo[:]:
                if xs[0] <= R:
                    a += 1
                    ufo.remove(xs)
                    continue
                elif flag:
                    r = xs[1]
                    pos = xs[2]
                    ufo.remove(xs)
                    flag = False
                    continue
                else:
                    d = xs[0] / xs[1] * abs(pos[0] * xs[2][1] - pos[1] * xs[2][0]) / r
                    if d <= xs[3]:
                        if xs[0] * math.cos(math.atan2(xs[2][1], xs[2][0]) - math.atan2(pos[1], pos[0])) + math.sqrt(xs[3] ** 2 - d ** 2) > R:
                            ufo.remove(xs)
        else:
            ans.append(a)

Submission status: Accepted

Solution code:
import math
ans = []
while True:
    ufo = []
    n = raw_input().split()
    if n == ["0", "0"]:
        for an in ans:
            print an
        break
    else:
        R = int(n[0])
        for i in range(int(n[1])):
            m = [int(f) for f in raw_input().split()]
            l = math.sqrt(m[0] ** 2 + m[1] ** 2)
            ufo.append([l, l, (m[0], m[1]), m[2], m[3]])
        a = 0
        while len(ufo) > 0:
            flag = True
            for xs in ufo: xs[0] -= xs[4]
            ufo.sort()
            for xs in ufo[:]:
                if xs[0] <= R:
                    a += 1
                    ufo.remove(xs)
                    continue
                elif flag:
                    r = xs[1]
                    pos = xs[2]
                    ufo.remove(xs)
                    flag = False
                    continue
                else:
                    d = xs[0] / xs[1] * abs(pos[0] * xs[2][1] - pos[1] * xs[2][0]) / r
                    if d <= xs[3]:
                        if xs[0] * math.cos(math.atan2(xs[2][1], xs[2][0]) - math.atan2(pos[1], pos[0])) + math.sqrt(xs[3] ** 2 - d ** 2) > R:
                            ufo.remove(xs)
        else:
            ans.append(a)

Submission status: Accepted

Solution code:
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.fpd=self.pd
		self.fpx=self.px
		self.fpy=self.py
		self.ex=self.fpx/self.fpd
		self.ey=self.fpy/self.fpd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.fpx*u.fpy-neu.fpy*u.fpx)/neu.fpd/u.fpd	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*cos(atan2(u.fpy,u.fpx)-atan2(neu.fpy,neu.fpx)) + sqrt(u.d**2-d**2) > R:
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.fpd=self.pd
		self.fpx=self.px
		self.fpy=self.py
		self.ex=self.fpx/self.fpd
		self.ey=self.fpy/self.fpd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*cos(atan2(u.fpy,u.fpx)-atan2(neu.fpy,neu.fpx)) + sqrt(u.d**2-d**2) > R:
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.fpd=self.pd
		self.fpx=self.px
		self.fpy=self.py
		self.ex=self.fpx/self.fpd
		self.ey=self.fpy/self.fpd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*cos(atan2(u.ey,u.ex)-atan2(neu.ey,neu.ex)) + sqrt(u.d**2-d**2) > R:
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.ex=self.px/self.pd
		self.ey=self.py/self.pd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*cos(atan2(u.ey,u.ex)-atan2(neu.ey,neu.ex)) + sqrt(u.d**2-d**2) > R:
				#if u.pd*abs(neu.ex*u.ex+neu.ey*u.ey)+sqrt(u.d**2-d**2) > R: #nazeka kore ja dame
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
from math import sqrt,cos,atan2

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.ex=self.px/self.pd
		self.ey=self.py/self.pd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				#if u.pd*cos(atan2(u.ey,u.ex)-atan2(neu.ey,neu.ex)) + sqrt(u.d**2-d**2) > R:
				if u.pd*(neu.ex*u.ex+neu.ey*u.ey)+sqrt(u.d**2-d**2) > R: #nazeka kore ja dame
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
from math import sqrt

class Ufo:
	def __init__(self,px,py,d,vd,ui):
		self.pd=sqrt(px**2+py**2)
		self.px=float(px)
		self.py=float(py)
		self.ex=self.px/self.pd
		self.ey=self.py/self.pd
		self.d=float(d)
		self.vd=float(vd)
		self.vx=-self.vd*self.ex
		self.vy=-self.vd*self.ey
		self.i=ui
	def move(self):
		self.pd -= self.vd
		self.px += self.vx
		self.py += self.vy



while True:
	R,ul=tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	us=[]
	for ui in xrange(ul):
		px,py,d,vd = tuple(map(int,raw_input().split()))
		u = Ufo(px,py,d,vd,ui)
		us.append(u)

	re=0
	while True:
		for u in us: u.move()
		us.sort(key=lambda u: u.pd)

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
				#print u.i, "due to invade"
				continue
			else:
				break
		if len(us)==0: break

		neu=us.pop(0)
		#print "focus",neu.i
		#print neu.i,"due to hit"

		for u in us[:]:
			d = u.pd*abs(neu.ex*u.ey-neu.ey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*(neu.ex*u.ex+neu.ey*u.ey)+sqrt(u.d**2-d**2) > R:
					us.remove(u)
					#print u.i, "due to hit"
		if len(us)==0: break

	print re

Submission status: Accepted

Solution code:
import math

class Ufo:
  def __init__(self, x, y, r, v):
    self.dist = get_dist(x, y)
    self.angle = get_angle(y, x)
    self.rad = r
    self.v = v

def get_dist(x, y):
  return (x ** 2 + y ** 2) ** (1 / 2)

def get_angle(x, y):
  angle = math.atan2(y, x)
  if angle < 0:
    angle += math.pi * 2
  return angle

def reache(ufos, R):
  remove_lst = []
  for i , ufo in enumerate(ufos):
    ufo.dist -= ufo.v
    if ufo.dist <= R:
      remove_lst.append(i)
  for i in reversed(remove_lst):
    ufos.pop(i)
  return len(remove_lst)

def is_dead(ufo, laser, R):
  diff = abs(ufo.angle - laser)
  if diff > math.pi:
    diff = math.pi * 2 - diff
  if (diff <= math.pi / 2 and ufo.dist * math.sin(diff) <= ufo.rad) or (ufo.dist <= ufo.rad):
    if ufo.dist * math.cos(diff) + (ufo.rad ** 2 - (ufo.dist * math.sin(diff)) ** 2) ** (1 / 2) > R:
      return True
  return False

def shoot(ufos, laser, R):
  remove_lst = []
  for i, ufo in enumerate(ufos):
    if is_dead(ufo, laser, R):
      remove_lst.append(i)
  for i in reversed(remove_lst):
    ufos.pop(i)

while True:
  R, n = map(int, input().split())
  if R == 0:
    break

  ufos = []
  for _ in range(n):
    x, y, r, v = map(int, input().split())
    ufos.append(Ufo(x, y, r, v))
  
  ans = 0
  while ufos:
    ans += reache(ufos, R)
    if ufos:
      laser = min(ufos, key=lambda ufo:ufo.dist).angle
      shoot(ufos, laser, R)
  print(ans)

Submission status: Accepted

Solution code:
import math

class Ufo:
  def __init__(self, x, y, r, v):
    self.dist = get_dist(x, y)
    self.angle = get_angle(y, x)
    self.rad = r
    self.v = v

def get_dist(x, y):
  return (x ** 2 + y ** 2) ** (1 / 2)

def get_angle(x, y):
  angle = math.atan2(y, x)
  if angle < 0:
    angle += math.pi * 2
  return angle

def reache(ufos, R):
  remove_lst = []
  for ufo in ufos:
    ufo.dist -= ufo.v
    if ufo.dist <= R:
      remove_lst.append(ufo)
  for ufo in remove_lst:
    ufos.remove(ufo)
  return len(remove_lst)

def is_dead(ufo, laser, R):
  diff = abs(ufo.angle - laser)
  if diff > math.pi:
    diff = math.pi * 2 - diff
  if (diff <= math.pi / 2 and ufo.dist * math.sin(diff) <= ufo.rad) or (ufo.dist <= ufo.rad):
    if ufo.dist * math.cos(diff) + (ufo.rad ** 2 - (ufo.dist * math.sin(diff)) ** 2) ** (1 / 2) > R:
      return True
  return False

def shoot(ufos, laser, R):
  remove_lst = []
  for ufo in ufos:
    if is_dead(ufo, laser, R):
      remove_lst.append(ufo)
  for ufo in remove_lst:
    ufos.remove(ufo)

while True:
  R, n = map(int, input().split())
  if R == 0:
    break

  ufos = []
  for _ in range(n):
    x, y, r, v = map(int, input().split())
    ufos.append(Ufo(x, y, r, v))
  
  ans = 0
  while ufos:
    ans += reache(ufos, R)
    if ufos:
      laser = min(ufos, key=lambda ufo:ufo.dist).angle
      shoot(ufos, laser, R)
  print(ans)

Submission status: Accepted

Solution code:
import math

class Ufo:
  def __init__(self, x, y, r, v):
    self.dist = get_dist(x, y)
    self.angle = get_angle(y, x)
    self.rad = r
    self.v = v

def get_dist(x, y):
  return (x ** 2 + y ** 2) ** (1 / 2)

def get_angle(x, y):
  angle = math.atan2(y, x)
  if angle < 0:
    angle += math.pi * 2
  return angle

def reach(ufos, R):
  remove_lst = []
  for ufo in ufos:
    ufo.dist -= ufo.v
    if ufo.dist <= R:
      remove_lst.append(ufo)
  for ufo in remove_lst:
    ufos.remove(ufo)
  return len(remove_lst)

def is_dead(ufo, laser, R):
  diff = abs(ufo.angle - laser)
  if diff > math.pi:
    diff = math.pi * 2 - diff
  if (diff <= math.pi / 2 and ufo.dist * math.sin(diff) <= ufo.rad) or (ufo.dist <= ufo.rad):
    if ufo.dist * math.cos(diff) + (ufo.rad ** 2 - (ufo.dist * math.sin(diff)) ** 2) ** (1 / 2) > R:
      return True
  return False

def shoot(ufos, laser, R):
  remove_lst = []
  for ufo in ufos:
    if is_dead(ufo, laser, R):
      remove_lst.append(ufo)
  for ufo in remove_lst:
    ufos.remove(ufo)

def main():
  while True:
    R, n = map(int, input().split())
    if R == 0:
      break
  
    ufos = []
    for _ in range(n):
      x, y, r, v = map(int, input().split())
      ufos.append(Ufo(x, y, r, v))
    
    ans = 0
    while ufos:
      ans += reach(ufos, R)
      if ufos:
        laser = min(ufos, key=lambda ufo:ufo.dist).angle
        shoot(ufos, laser, R)
    print(ans)
main()

Submission status: Accepted

Solution code:
while(True):
    ans = 0
    R, N = map(int, input().split())
    R = float(R)
    if R == 0 and N == 0:
        break
    d = []
    for _ in range(N):
        d.append(list(map(float, input().split())))
    for i in range(len(d)-1,-1,-1):
        x,y = d[i][0],d[i][1]
        d[i][0] = (x**2+y**2)**0.5
        d[i].append(x/d[i][0])
        d[i].append(y/d[i][0])
        if d[i][0] <= R:
            ans += 1
            del d[i]
    while(True):
        if not len(d): print(ans); break
        for i in range(len(d)-1,-1,-1):
            d[i][0] -= d[i][3]
            if d[i][0] <= R:
                ans += 1
                del d[i]
        if not len(d): print(ans); break
        d.sort(key=lambda x: x[0])
        for j in range(len(d)-1,0,-1):
            X = d[j][0]*d[j][4]
            Y = d[j][0]*d[j][5]
            if (d[j][4]*d[0][4]+d[j][5]*d[0][5] ) < 0:
                xv = R*d[0][4]
                yv = R*d[0][5]
                if ((X-xv)**2+(Y-yv)**2)**0.5 < d[j][2]:
                    del d[j]
                continue
            if ( abs((d[0][5]*X-d[0][4]*Y)) < d[j][2] ):
                del d[j]
        del d[0]