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:
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.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*abs(neu.fpx*u.fpx+neu.fpy*u.fpy)/neu.fpd/u.fpd + 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: Wrong Answer

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:
				if u.pd*abs(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: Wrong Answer

Solution code:
def simulate(r, u):
    cnt = 0
    while len(u):
        for ui in u:
            ui.progress()
        
        pre = len(u)
        u = [ui for ui in u if r < ui.d]
        cnt += pre - len(u)
        
        if len(u) == 0:
            break
        near_u = min(u,key=operator.attrgetter('d'))
        l = laser(near_u)
        u = [ui for ui in u if not l.is_hit(ui)]
    return cnt
import math
class laser:
    def __init__(self, u):
        if u.x == 0:
            self.a = 1
            self.b = 0
        elif u.y == 0:
            self.a = 0
            self.b = 1
        else:
            denominator = math.sqrt(u.x * u.x + u.y * u.y)
            self.a = u.x / denominator
            self.b = -u.y / denominator
    def is_hit(self, u):
        return abs(self.a * u.x + self.b * u.y) <= u.r
class ufo:
    def __init__(self, x, y, r, v):
        self.x = x
        self.y = y
        self.r = r
        self.v = v
        self.d = math.sqrt(x * x + y * y)
    def progress(self):
        rate = (self.d - self.v) / self.d
        self.x *= rate
        self.y *= rate
        self.d -= self.v

import sys
f = sys.stdin


import operator

while True:
    r, n = map(int, f.readline().split())
    if n == 0:
        break
    u = [ufo(*list(map(int, f.readline().split()))) for _ in range(n)]
    print(simulate(r, u))

Submission status: Wrong Answer

Solution code:
def simulate(r, u):
    cnt = 0
    while len(u):
        for ui in u:
            ui.progress()
        
        pre = len(u)
        u = [ui for ui in u if r < ui.d]
        cnt += pre - len(u)
        
        if len(u) == 0:
            break
        near_u = min(u,key=operator.attrgetter('d'))
        l = laser(near_u)
        u = [ui for ui in u if not l.is_hit(ui)]
    return cnt
import math
class laser:
    def __init__(self, u):
        x,y = u.init_p
        if x == 0:
            self.a = 1
            self.b = 0
        elif y == 0:
            self.a = 0
            self.b = 1
        else:
            denominator = math.sqrt(x * x + y * y)
            self.a = y / denominator
            self.b = -x / denominator
    def is_hit(self, u):
        return abs(self.a * u.x + self.b * u.y) <= u.r
class ufo:
    def __init__(self, x, y, r, v):
        self.init_p = (x,y)
        self.x = x
        self.y = y
        self.r = r
        self.v = v
        self.d = math.sqrt(x * x + y * y)
    def progress(self):
        rate = (self.d - self.v) / self.d
        self.x *= rate
        self.y *= rate
        self.d -= self.v

import sys
f = sys.stdin

import operator

while True:
    r, n = map(int, f.readline().split())
    if n == 0:
        break
    u = [ufo(*list(map(int, f.readline().split()))) for _ in range(n)]
    print(simulate(r, u))

Submission status: Wrong Answer

Solution code:
import heapq
import math


while(1):
    [R,N]=[int(x) for x in raw_input().split()]
    if R==0:
        break
    else:
        ufoheap=[]
        passed=0
        for i in range(N):
            [x0,y0,r,v]=[int(x) for x in raw_input().split()]
            d=math.sqrt(x0**2+y0**2)-v
            theta=math.atan2(y0,x0)
            if d<=R:
                passed=passed+1
            else:
                heapq.heappush(ufoheap,(d,theta,r,v))
        while (len(ufoheap)>0):
            closestufo=heapq.heappop(ufoheap)
            fay=closestufo[1]
            #checkifhit
            newheap=[]
            for ufo in ufoheap:
                [d,theta,r,v]=ufo
                if abs(d*math.sin(theta-fay))>r:
                    d=d-v
                    if d<=R:
                        passed=passed+1
                    else:
                        heapq.heappush(newheap,(d,theta,r,v))
            ufoheap=newheap
        print passed

Submission status: Wrong Answer

Solution code:
import heapq
import math


while(1):
    [R,N]=[int(x) for x in raw_input().split()]
    if R==0:
        break
    else:
        ufoheap=[]
        passed=0
        for i in range(N):
            [x0,y0,r,v]=[int(x) for x in raw_input().split()]
            d=math.sqrt(x0**2+y0**2)-v
            theta=math.atan2(y0,x0)
            if d<=R:
                passed=passed+1
            else:
                heapq.heappush(ufoheap,(d,theta,r,v))
        while (len(ufoheap)>0):
            closestufo=heapq.heappop(ufoheap)
            #if len(ufoheap)>0:
            #    closestufo2=heapq.heappop(ufoheap)
            #else:
            #    closestufo2=[-1,-1,-1,-1]
            newheap=[]
            #if there is 2 ufo at same dist
            #if closestufo[0]==closestufo2[0]:
            #    print 'same'
            #    ufoheap=[closestufo,closestufo2]+ufoheap
            #    for ufo in ufoheap:
            #        [d,theta,r,v]=ufo
            #        d=d-v
            #        if d<=R:
            #            passed=passed+1
            #        else:
            #            heapq.heappush(newheap,(d,theta,r,v))
            #    ufoheap=newheap
            #else:
            #if closestufo2[0]!=-1:
            #    ufoheap=[closestufo2]+ufoheap
            fay=closestufo[1]
            for ufo in ufoheap:
                [d,theta,r,v]=ufo
                #check if hit
                hit=0
                if abs(d*math.sin(theta-fay))==r:
                    point=(d*math.cos(theta-fay)*math.cos(fay),d*math.cos(theta-fay)*math.sin(fay))
                    if math.atan2(point[1],point[0])==fay:
                            hit==1
                elif abs(d*math.sin(theta-fay))<r:
                    point=((d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    point2=((d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    if math.atan2(point[1],point[0])==fay or math.atan2(point2[1],point2[0])==fay:
                            hit==1
                if not hit:
                    d=d-v
                    if d<=R:
                        passed=passed+1
                    else:
                        heapq.heappush(newheap,(d,theta,r,v))
            ufoheap=newheap
        print passed

Submission status: Wrong Answer

Solution code:
import heapq
import math


while(1):
    [R,N]=[int(x) for x in raw_input().split()]
    if R==0:
        break
    else:
        ufoheap=[]
        passed=0
        for i in range(N):
            [x0,y0,r,v]=[int(x) for x in raw_input().split()]
            d=math.sqrt(x0**2+y0**2)-v
            theta=math.atan2(y0,x0)
            if d<=R:
                passed=passed+1
            else:
                heapq.heappush(ufoheap,(d,theta,r,v))
        while (len(ufoheap)>0):
            closestufo=heapq.heappop(ufoheap)
            #if len(ufoheap)>0:
            #    closestufo2=heapq.heappop(ufoheap)
            #else:
            #    closestufo2=[-1,-1,-1,-1]
            newheap=[]
            #if there is 2 ufo at same dist
            #if closestufo[0]==closestufo2[0]:
            #    print 'same'
            #    ufoheap=[closestufo,closestufo2]+ufoheap
            #    for ufo in ufoheap:
            #        [d,theta,r,v]=ufo
            #        d=d-v
            #        if d<=R:
            #            passed=passed+1
            #        else:
            #            heapq.heappush(newheap,(d,theta,r,v))
            #    ufoheap=newheap
            #else:
            #if closestufo2[0]!=-1:
            #    ufoheap=[closestufo2]+ufoheap
            fay=closestufo[1]
            for ufo in ufoheap:
                [d,theta,r,v]=ufo
                #check if hit
                hit=0
                if abs(d*math.sin(theta-fay))==r:
                    point=(d*math.cos(theta-fay)*math.cos(fay),d*math.cos(theta-fay)*math.sin(fay))
                    if abs(math.atan2(point[1],point[0])-fay)<10**-6:
                            hit=1
                elif abs(d*math.sin(theta-fay))<r:
                    point=((d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    point2=((d*math.cos(theta-fay)+math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)+math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    if abs(math.atan2(point[1],point[0])-fay)<10**-6 or abs(math.atan2(point2[1],point2[0])-fay)<10**-6:
                            hit=1
                if not hit:
                    d=d-v
                    if d<=R:
                        passed=passed+1
                    else:
                        heapq.heappush(newheap,(d,theta,r,v))
            ufoheap=newheap
        print passed

Submission status: Wrong Answer

Solution code:
import heapq
import math


while(1):
    [R,N]=[int(x) for x in raw_input().split()]
    if R==0:
        break
    else:
        ufoheap=[]
        passed=0
        for i in range(N):
            [x0,y0,r,v]=[int(x) for x in raw_input().split()]
            d=math.sqrt(x0**2+y0**2)-v
            theta=math.atan2(y0,x0)
            if d<=R:
                passed=passed+1
            else:
                heapq.heappush(ufoheap,(d,theta,r,v))
        #print ufoheap
        while (len(ufoheap)>0):
            closestufo=heapq.heappop(ufoheap)
            #if len(ufoheap)>0:
            #    closestufo2=heapq.heappop(ufoheap)
            #else:
            #    closestufo2=[-1,-1,-1,-1]
            newheap=[]
            #if there is 2 ufo at same dist
            #if closestufo[0]==closestufo2[0]:
            #    print 'same'
            #    ufoheap=[closestufo,closestufo2]+ufoheap
            #    for ufo in ufoheap:
            #        [d,theta,r,v]=ufo
            #        d=d-v
            #        if d<=R:
            #            passed=passed+1
            #        else:
            #            heapq.heappush(newheap,(d,theta,r,v))
            #    ufoheap=newheap
            #else:
            #if closestufo2[0]!=-1:
            #    ufoheap=[closestufo2]+ufoheap
            fay=closestufo[1]
            for ufo in ufoheap:
                [d,theta,r,v]=ufo
                #check if hit
                hit=0
                if abs(d*math.sin(theta-fay))==r:
                    point=(d*math.cos(theta-fay)*math.cos(fay),d*math.cos(theta-fay)*math.sin(fay))
                    if abs(math.atan2(point[1],point[0])-fay)<10**-6:
                            hit=1
                elif abs(d*math.sin(theta-fay))<r:
                    point=((d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    point2=((d*math.cos(theta-fay)+math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.cos(fay),(d*math.cos(theta-fay)+math.sqrt(r**2-d*math.sin(theta-fay)**2))*math.sin(fay))
                    if (abs(math.atan2(point[1],point[0])-fay)<10**-6 and abs(d*math.cos(theta-fay)-math.sqrt(r**2-d*math.sin(theta-fay)**2))>R) or (abs(math.atan2(point2[1],point2[0])-fay)<10**-6 and abs(d*math.cos(theta-fay)+math.sqrt(r**2-d*math.sin(theta-fay)**2))>R):
                            hit=1
                if not hit:
                    d=d-v
                    if d<=R:
                        passed=passed+1
                    else:
                        heapq.heappush(newheap,(d,theta,r,v))
            ufoheap=newheap
            #print ufoheap
        print passed

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# AOJ:0204
from operator import itemgetter, attrgetter
import math
class UFO:
    def __init__(self, x0, y0, r, v):
        self.radius = r
        self.v = v
        self.x = x0
        self.y = y0
        self.R = math.sqrt(self.x**2 + self.y**2) 
        self.theta = math.atan2(self.y, self.x) 
        self.cos = math.cos(self.theta)
        self.sin = math.sin(self.theta)
        self.isalive = True
        
    def __repr__(self):
        return repr((self.R, self.theta, self.isalive))
        
    def set_UFO_position(self, t):
        self.R = self.R - self.v * t
        self.theta = math.atan2(self.y, self.x) 
        self.cos = math.cos(self.theta)
        self.sin = math.sin(self.theta)
#    
def is_makizoeUFO(makizoeUFO, shootedUFO):
    d = makizoeUFO.R * math.sin(abs(makizoeUFO.theta - shootedUFO.theta)) 
    if d <= makizoeUFO.radius:
	    return True
    else:
	    return False
	
if __name__ == "__main__":
    while True:
        R, N = map(int,raw_input().split())
        if (R,N) == (0,0):
            break
        UFOs = []
        for i in xrange(N):
            x0, y0, r, v = map(int,raw_input().split())
            ufo = UFO(x0, y0, r, v)
            UFOs.append(ufo)
        
        time = 1
        inRUFOnum = 0
        endUFOnum = 0
        while True: 
            for i in xrange(N): 
                if UFOs[i].isalive:
                    UFOs[i].set_UFO_position(time)
                UFOs = sorted(UFOs, key = lambda UFO: UFO.R)
                if UFOs[i].isalive :
                    if  UFOs[i].radius + R > UFOs[i].R:
                        inRUFOnum += 1
                        UFOs[i].isalive = False
                        endUFOnum += 1
                    else:
                        for j in range(N):
                            if (UFOs[j].isalive and (UFOs[j].R >= R)) or (UFOs[j].isalive and UFOs[j].R * (UFOs[j].R - UFOs[j].v ) < 0): 
                                theUFO = UFOs[j]
                                theUFO.isalive = False
                                endUFOnum += 1
                                for k in range(N):
                                    if is_makizoeUFO(theUFO, UFOs[k]):
                                        if UFOs[k].isalive:
                                            UFOs[k].isalive = False
                                            endUFOnum += 1
                                break
            time += 1
            if endUFOnum == N:
                print inRUFOnum
                break

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll < (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if (l - t*v)*abs(x0*y - x*y0) < r*l*l0 + 1e-8:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll <= (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if (l - t*v)*abs(x0*y - x*y0) < r*l*l0 + 1e-8:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll <= (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            A = abs(x0*y - x*y0)
            B = t*v
            if A**2 <= r**2*ll0 or 4*A**2*r**2*ll0*ll**2 >= (A**2*(ll-B**2)+ll0)**2:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll <= (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            A = abs(x0*y - x*y0)
            B = t*v
            if A**2 <= r**2*ll0 or 4*A**2*r**2*ll0*ll**2 >= (A**2*(ll-B**2)+r**2*ll0*ll)**2:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll <= (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        A = x0**2 + y0**2
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            B = x*x0 + y*y0
            C = x**2 + y**2 - r**2
            if B**2 < A*C:
                continue
            if R-B < sqrt(B**2 - A*C) + 1e-8:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    ans = 0
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            if ll <= (R + t*v)**2:
                kill[i] = 1
                ans += 1

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        A = x0**2 + y0**2
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            B = x*x0 + y*y0
            C = x**2 + y**2 - r**2
            if B**2 < A*C:
                continue
            if B >= 0 or A*C <= 0:
                kill[i] = 1
    print ans

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i] or ll <= (R + t*v)**2:
                continue

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        A = x0**2 + y0**2
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            B = x*x0 + y*y0
            C = x**2 + y**2 - r**2
            if B**2 < A*C:
                continue
            if R<B or (R-B)**2 <= B**2 - A*C:
                kill[i] = 1
    print N-sum(kill)

Submission status: Wrong Answer

Solution code:
from math import sqrt
while 1:
    R, N = map(int, raw_input().split())
    if R == N == 0:
        break
    P = []
    for i in xrange(N):
        x, y, r, v = map(int, raw_input().split())
        P.append((sqrt(x**2+y**2), x**2+y**2, x, y, r, v, i))
    kill = [0]*N
    for t in xrange(1, N+1):
        j = None; mi = 10**9
        for l, ll, x, y, r, v, i in P:
            if kill[i] or ll <= (R + t*v)**2:
                continue

            if not kill[i] and l - t*v < mi:
                mi = l - t*v
                j = i
        if j is None:
            break
        l0, ll0, x0, y0, r0, v0, j = P[j]
        A = x0**2 + y0**2
        for l, ll, x, y, r, v, i in P:
            if kill[i]:
                continue
            B = x*x0 + y*y0
            C = x**2 + y**2 - r**2
            if B**2 < A*C:
                continue
            if ll > t**2*v**2 and (R<B or (R-B)**2 <= B**2 - A*C):
                kill[i] = 1
    print N-sum(kill)

Submission status: Wrong Answer

Solution code:
import math

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 move(ufos, R):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    ufos[i][0] -= ufos[i][3]
    if ufos[i][0] <= R:
      remove_lst.append(i)
  
  for i in reversed(remove_lst):
    ufos.pop(i)
  return len(remove_lst)


def is_dead(ufo, laser):
  dist = ufo[0]
  angle = ufo[1]
  rad = ufo[2]
  diff = abs(angle - laser)
  if diff < math.pi / 2 and math.sin(diff) * dist <= rad:
    return True
  else:
    return False

def shoot(ufos, laser):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    if is_dead(ufos[i], laser):
      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([get_dist(x, y), get_angle(x, y), r, v])
  ufos.sort()
  
  ans = 0
  while ufos:
    ans += move(ufos, R)
    if ufos:
      ufos.sort()
      laser = ufos[0][1]
      shoot(ufos, laser)
  print(ans)

Submission status: Wrong Answer

Solution code:
import math

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 move(ufos, R):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    ufos[i][0] -= ufos[i][3]
    if ufos[i][0] <= R:
      remove_lst.append(i)
  
  for i in reversed(remove_lst):
    ufos.pop(i)
  return len(remove_lst)


def is_dead(ufo, laser):
  dist = ufo[0]
  angle = ufo[1]
  rad = ufo[2]
  diff = abs(angle - laser)
  if diff > math.pi:
    diff = math.pi * 2 - diff
  if diff < math.pi / 2 and math.sin(diff) * dist <= rad:
    return True
  else:
    return False

def shoot(ufos, laser):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    if is_dead(ufos[i], laser):
      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([get_dist(x, y), get_angle(x, y), r, v])
  ufos.sort()
  
  ans = 0
  while ufos:
    ans += move(ufos, R)
    if ufos:
      ufos.sort()
      laser = ufos[0][1]
      shoot(ufos, laser)
  print(ans)

Submission status: Wrong Answer

Solution code:
import math

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 move(ufos, R):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    ufos[i][0] -= ufos[i][3]
    if ufos[i][0] <= R:
      remove_lst.append(i)
  
  for i in reversed(remove_lst):
    ufos.pop(i)
  return len(remove_lst)


def is_dead(ufo, laser):
  dist = ufo[0]
  angle = ufo[1]
  rad = ufo[2]
  diff = abs(angle - laser)
  if diff > math.pi:
    diff = math.pi * 2 - diff
  if (diff < math.pi / 2 and math.sin(diff) * dist <= rad) or dist <= r:
    return True
  else:
    return False

def shoot(ufos, laser):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    if is_dead(ufos[i], laser):
      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([get_dist(x, y), get_angle(x, y), r, v])
  ufos.sort()
  
  ans = 0
  while ufos:
    ans += move(ufos, R)
    if ufos:
      ufos.sort()
      laser = ufos[0][1]
      shoot(ufos, laser)
  print(ans)

Submission status: Wrong Answer

Solution code:
import math

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 move(ufos, R):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    ufos[i][0] -= ufos[i][3]
    if ufos[i][0] <= R:
      remove_lst.append(i)
  
  for i in reversed(remove_lst):
    ufos.pop(i)
  return len(remove_lst)


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

def shoot(ufos, laser):
  length = len(ufos)
  remove_lst = []
  for i in range(length):
    if is_dead(ufos[i], laser):
      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([get_dist(x, y), get_angle(x, y), r, v])
  ufos.sort()
  
  ans = 0
  while ufos:
    ans += move(ufos, R)
    if ufos:
      ufos.sort()
      laser = ufos[0][1]
      shoot(ufos, laser)
  print(ans)