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,fabs,ceil,floor,pow,exp,log,sin,cos,tan,asin,acos,atan,atan2,pi



eps=1e-10
inf=float("inf")

class Angle:	#angle. kaku.
	def __init__(self,th):
		self.th = float(th)%(2*pi)
	def __float__(self):
		return self.th
	def __eq__(self,other):
		return fabs(float(self)-float(other))<eps or fabs(fabs(float(self)-float(other))-2*pi)<eps
	def isParaWith(self,other):
		return self==other or self==other+pi
	def __add__(self,other):
		return Angle( (float(self) + float(other)) % (2*pi) )
	def __sub__(self,other):
		return Angle( (float(self) - float(other)) % (2*pi) )
	def __mul__(self,c):
		return Angle( (float(self) * c) % (2*pi) )
	def __rmul__(self,c):
		return Angle( (float(self) * c) % (2*pi) )
	def __div__(self,c):
		return Angle( (float(self) / c) % (2*pi) )
	def __repr__(self):
		return "Angle("+str(float(self))+")"

class Vector:	#point, vector. ten, bekutoru.
	def __init__(self,x=None,y=None,d=None,th=None):
		if not(x is None) and not(y is None):
			self.setXY(x,y)
		if not(d is None) and not(th is None):
			self.setDTh(d, th)
	def setXY(self,x,y):
		self.x=float(x);
		self.y=float(y);
		self.calcFromXY()
	def setDTh(self,d,th):
		self.d=float(d)
		self.th=Angle(th)
		self.calcFromDTh()
	def calcFromXY(self):
		self.d=sqrt(self.x**2+self.y**2)
		self.th=Angle(atan2(self.y,self.x))
	def calcFromDTh(self):
		self.x=self.d*cos(self.th)
		self.y=self.d*sin(self.th)
	def __eq__(self,other):
		return fabs(self.x-other.x)<eps and fabs(self.y-other.y)<eps
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,other):
		return Vector(self.x+other.x, self.y+other.y)
	def __sub__(self,other):
		return Vector(self.x-other.x, self.y-other.y)
	def __neg__(self):
		return Vector(-self.x, -self.y)
	def __mul__(self,c):
		return Vector(self.x*c, self.y*c)
	def __rmul__(self,c):
		return Vector(self.x*c, self.y*c)
	def __div__(self,c):
		return Vector(self.x/c, self.y/c)
	def __abs__(self):
		return self.d
	def rotated(self,th):
		v=Vector(d=self.d, th=self.th+th)
		return v
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def inprod(self,other):
		return self.x*other.x+self.y*other.y
	def outprod(self,other):
		return self.x*other.y-self.y*other.x
	def isOn(self,obj):
		if isinstance(obj,DirSegLine) or isinstance(obj,SegLine):
			return obj.ap==self or obj.bp==self or (obj.th==(self-obj.ap).th and obj.th==(obj.bp-self).th)
		if isinstance(obj,HalfLine):
			return obj.ap==self or obj.th==(self-obj.ap).th
		if isinstance(obj,Line):
			return obj.th==(self-obj.ap).th or obj.th==(obj.bp-self).th
		if isinstance(obj,Circle):
			return abs(abs(self-obj.p)-obj.d)<eps
	def isIn(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)<obj.d
	def isOut(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)>obj.d
	def __repr__(self):
		return "Vector("+str(self.x)+", "+str(self.y)+")"

Point=Vector

class DirSegLine:	#directed line segment. yuukou senbun.
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=ap
		self.bp=bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.bp==other.bp
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return DirSegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return DirSegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return self.d
	def rotated(self,th):
		return DirSegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p

class SegLine:	#line segmeny. senbun.
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=ap
		self.bp=bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = self.dv.th
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp) or (self.ap==other.bp and self.bp==other.ap)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return SegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return SegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return self.d
	def rotated(self,th):
		return SegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p

class HalfLine:
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
	def setApBp(self,ap,bp):
		self.ap=ap
		self.bp=bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.th==other.th
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return HalfLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return HalfLine(self.ap-v, self.bp-v)
	def rotated(self,th):
		return HalfLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p

class Line:
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
		if not(bp is None) and not(th is None): self.setApBp(bp-Vector(d=1,th=th), bp)
	def setApBp(self,ap,bp):
		self.ap=ap
		self.bp=bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = self.dv.th
	def __eq__(self,other):
		#return ( self.ap==other.ap or self.ap==other.bp or (self.ap-other.ap).isParaWith(other.dv) )	\
		#	and( self.bp==other.ap or self.bp==other.bp or (self.bp-other.bp).isParaWith(other.dv) )
		return self.ap.isOn(other) and self.bp.isOn(other)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return Line(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return Line(self.ap-v, self.bp-v)
	def rotated(self,th):
		return Line(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p

class Circle:
	def __init__(self,p,d):
		self.setPD(p,d)
	def setPD(self,p,d):
		self.p=p
		self.d=d
	def __eq__(self,other):
		return self.p==other.p and abs(self.d-other.d)<eps
	def __add__(self,v):
		return Circle(self.p+v, self.d)
	def __sub__(self,v):
		return Circle(self.p-v, self.d)
	def rotated(self,th):
		return Circle(self.p.rotated(th), self.d)
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p

class Triangle:
	def __init__(self,ap,bp,cp):
		self.setApBpCp(ap,bp,cp)
	def setApBpCp(self,ap,bp,cp):
		self.ap=ap
		self.bp=bp
		self.cp=cp
		self.calcFromApBpCp(ap, bp, cp)
	def calcFromApBpCp(self,ap,bp,cp):
		self.ae=SegLine(bp,cp)
		self.be=SegLine(cp,ap)
		self.ce=SegLine(ap,bp)
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp and self.cp==other.cp) \
			or (self.ap==other.bp and self.bp==other.cp and self.cp==other.ap) \
			or (self.ap==other.cp and self.bp==other.ap and self.cp==other.bp)
	def __add__(self,v):
		return Triangle(self.ap+v,self.bp+v,self.cp+v)
	def __sub__(self,v):
		return Triangle(self.ap-v,self.bp-v,self.cp-v)
	def rotated(self,th):
		return Triangle(self.ap.rotated(th),self.bp.rotated(th),self.cp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def area(self):
		return abs((self.cp-self.ap).outprod(self.bp-self.cp))/2
	def gravityCenter(self):	#juushin
		return (self.ap+self.bp+self.cp)/3
	def innerCenter(self):		#naishin
		return crossPoints(angleBisector(self.ae,self.be), angleBisector(self.be,self.ce))[0]
	def exterCenter(self):		#gaishin
		return crossPoints(perpendicularBisector(self.ae), perpendicularBisector(self.be))[0]
	def orthoCenter(self):		#suishin
		return crossPoints(perpendicular(self.ap,self.ae), perpendicular(self.bp,self.be))[0]

def crossPoints(m,n):
	if (isinstance(m,DirSegLine) or isinstance(m,SegLine) or isinstance(m,HalfLine) or isinstance(m,Line)) \
			and (isinstance(n,DirSegLine) or isinstance(n,SegLine) or isinstance(n,HalfLine) or isinstance(n,Line)):
		c = m.dv.outprod(n.dv)
		if abs(c)<eps: return []
		s = n.dv.outprod(m.ap-n.ap) / c
		t = m.dv.outprod(n.ap-m.ap) / c
		if (     ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=s<=1)	\
			or   (isinstance(m,HalfLine) and 0<=s)									\
			or   (isinstance(m,Line))												\
		   )and( ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=t<=1)	\
			or   (isinstance(m,HalfLine) and 0<=t)									\
			or   (isinstance(m,Line))												\
			):
		   return [m.ap+m.dv*s]
	if (isinstance(m,DirSegLine) or isinstance(m,SegLine) or isinstance(m,HalfLine) or isinstance(m,Line)) \
			and isinstance(n,Circle):
		l=perpendicular(n.p, m)
		if l.bp.isOn(n):
			return [l.bp]
		if l.bp.isOut(n):
			return []
		if l.bp.isIn(n):
			r=sqrt(n.d**2-l.d**2)
			return [l.bp+Vector(d=r,th=l.th+pi/2), l.bp+Vector(d=r,th=l.th-pi/2)]
	if isinstance(m,Circle) \
			and (isinstance(n,DirSegLine) or isinstance(n,SegLine) or isinstance(n,HalfLine) or isinstance(n,Line)):
		return crossPoints(n, m)
	if isinstance(m,Circle) and isinstance(n,Circle):
		if m.p==n.p and abs(m.d-n.d)<eps:		#itchi
			return []
		if abs( abs(m.p-n.p)-(m.d-n.d) )<eps:	#naisetsu(n in m)
			return [(n.p*m.d-m.p*n.d)/(m.d-n.d)]
		if abs(m.p-n.p) < (m.d-n.d):			#naihou(n in m)
			return []
		if abs( abs(m.p-n.p)-(n.d-m.d) )<eps:	#naisetsu(m in n)
			return [(m.p*n.d-n.p*m.d)/(n.d-m.d)]
		if abs(m.p-n.p) < (n.d-m.d):			#naihou(n in m)
			return []
		if abs( abs(m.p-n.p)-(m.d+n.d) )<eps:	#gaisetsu
			return [(m.p*n.d+n.p*m.d)/(m.d+n.d)]
		if abs(m.p-n.p) > (m.d+n.d):			#hanareteru
			return []
		if abs(m.p-n.p) < (m.d+n.d):
			d = abs(m.p-n.p)
			x = (d**2+m.d**2-n.d**2)/(2*d)
			y = sqrt(m.d**2-x**2)
			v1 = Vector(x,y)
			v2 = Vector(x,-y)
			th = (n.p-m.p).th
			return [m.p+v1.rotated(th), m.p+v2.rotated(th)]

def perpendicular(p,m):
	m=Line(m.ap,m.bp)
	ap=p
	th=m.th+pi/2
	bp=crossPoints(m, Line(ap=ap,th=th))[0]
	return DirSegLine(ap,bp)

def angleBisector(m,n):
	if m.isParaWith(n):
		return Line(ap=(m.ap+n.ap)/2,th=m.th)
	else:
		return Line(ap=crossPoints(Line(m.ap,m.bp),Line(n.ap,n.bp))[0], th = (m.th+n.th)/2)

def perpendicularBisector(m):
	return Line(ap=(m.ap+m.bp)/2,th=m.th+pi/2)


class Ufo:
	def __init__(self,px,py,d,vd,i):
		p=Vector(px,py)
		self.p=p
		self.d=d
		self.c=Circle(p,d)
		self.v=-p/abs(p)*vd
		self.i=i
	def move(self): #genten toottaka wo kaesu
		if(abs(self.p)<=abs(self.v)): return True
		self.p=self.p+self.v
		self.c=self.c+self.v
		return False

class Raser:
	def __init__(self,ap,bp):
		self.line = HalfLine(ap=Vector(0,0),bp=bp)


while True:
	R,ul = tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	ignArea = Circle(Vector(0,0),R)
	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:
		rus=[] #us to be removed
		for u in us:
			passed = u.move()
			if passed or u.p.isIn(ignArea):
				re+=1
				rus.append(u)
		for u in rus:
			#print u.i, "removed due to it invaded inside"
			us.remove(u)

		if len(us)==0:
			break

		neu=Ufo(inf,inf,1,1,1000)
		for u in us:
			if abs(u.p)<abs(neu.p):
				neu=u
		raser = Raser(neu.p/abs(neu.p)*R ,neu.p)

		rus=[]
		for u in us:
			if len(crossPoints(raser.line, u.c))!=0:
				#print u.i, "removed due to raser hit"
				rus.append(u)
		for u in rus:
			us.remove(u)

		if len(us)==0:
			break

	print re

Submission status: Wrong Answer

Solution code:
from math import sqrt,fabs,ceil,floor,pow,exp,log,sin,cos,tan,asin,acos,atan,atan2,pi
import copy


inf=float("inf")


class Real:
	isLineLike=False
	eps=1e-10
	def __init__(self,x):
		self.x=float(x)
	def __float__(self):
		return self.x
	def __repr__(self):
		return str(self.x)
	def __eq__(self,other):
		return abs( float(self) - float(other) ) <= Real.eps
	def __ne__(self,other):
		return abs( float(self) - float(other) ) > Real.eps
	def __lt__(self,other):
		return float(self) < float(other)
	def __le__(self,other):
		return float(self) <= float(other) + Real.eps
	def __gt__(self,other):
		return float(self) > float(other)
	def __ge__(self,other):
		return float(self) + Real.eps >= float(other)
	def __add__(self,other):
		return Real(float(self)+float(other))
	def __sub__(self,other):
		return Real(float(self)-float(other))
	def __mul__(self,other):
		return Real(float(self)*float(other))
	def __div__(self,other):
		return Real(float(self)/float(other))
	def __mod__(self,other):
		return Real(float(self)%float(other))
	def __pow__(self,c):
		return Real(float(self)**c)
	def __rmul__(self,other):
		return Real(float(other)*float(self))
	def __pos__(self):
		return Real(float(self))
	def __neg__(self):
		return Real(-float(self))
	def __abs__(self):
		return Real(abs(float(self)))

class Angle:	#angle. kaku.
	isLineLike=False
	def __init__(self,th):
		self.th = Real(th)%(2*pi)
	def __float__(self):
		return float(self.th)
	def __repr__(self):
		return "Angle("+str(Real(self))+")"
	def __eq__(self,other):
		return Real(self)==Real(other) or abs(Real(self)-Real(other))==Real(2*pi)
	def isParaWith(self,other):
		return self==other or self==other+pi
	def __add__(self,other):
		return Angle( Real(self) + Real(other) )
	def __sub__(self,other):
		return Angle( Real(self) - Real(other) )
	def __mul__(self,c):
		return Angle( Real(self) * Real(c) )
	def __div__(self,c):
		return Angle( Real(self) / Real(c) )
	def __rmul__(self,c):
		return Angle( Real(c) * Real(self) )
	def __pos__(self):
		return Angle(Real(self))
	def __neg__(self):
		return Angle(-Real(self))
	def __abs__(self):
		return Angle(abs(Real(self)))

class Vector:	#point, vector. ten, bekutoru.
	isLineLike=False
	def __init__(self,x=None,y=None,d=None,th=None):
		if not(x is None) and not(y is None):
			self.setXY(x,y)
		if not(d is None) and not(th is None):
			self.setDTh(d,th)
	def setXY(self,x,y):
		self.x=Real(x);
		self.y=Real(y);
		self.calcFromXY()
	def setDTh(self,d,th):
		self.d=Real(d)
		self.th=Angle(th)
		self.calcFromDTh()
	def calcFromXY(self):
		self.d=sqrt(self.x**2+self.y**2)
		self.th=Angle(atan2(self.y,self.x))
	def calcFromDTh(self):
		self.x=self.d*cos(self.th)
		self.y=self.d*sin(self.th)
	def e(self):
		return self/self.d
	def __eq__(self,other):
		return self.x==other.x and self.y==other.y
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,other):
		return Vector(self.x+other.x, self.y+other.y)
	def __sub__(self,other):
		return Vector(self.x-other.x, self.y-other.y)
	def __mul__(self,c):
		return Vector(self.x*c, self.y*c)
	def __div__(self,c):
		return Vector(self.x/c, self.y/c)
	def __rmul__(self,c):
		return Vector(c*self.x, c*self.y)
	def __pos__(self):
		return Vector(self.x, self.y)
	def __neg__(self):
		return Vector(-self.x, -self.y)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return Vector(d=self.d, th=self.th+th)
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def inprod(self,other):
		return self.x*other.x+self.y*other.y
	def outprod(self,other):
		return self.x*other.y-self.y*other.x
	def isOn(self,obj):
		if isinstance(obj,DirSegLine) or isinstance(obj,SegLine):
			return obj.ap==self or obj.bp==self or (obj.th==(self-obj.ap).th and obj.th==(obj.bp-self).th)
		if isinstance(obj,HalfLine):
			return obj.ap==self or obj.th==(self-obj.ap).th
		if isinstance(obj,Line):
			return obj.th==(self-obj.ap).th or obj.th==(obj.bp-self).th
		if isinstance(obj,Circle):
			return abs(self-obj.p)==obj.d
	def isIn(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)<obj.d
	def isOut(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)>obj.d
	def __repr__(self):
		return "Vector("+str(self.x)+", "+str(self.y)+")"

Point=Vector

class DirSegLine:	#directed line segment. yuukou senbun.
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = +self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.bp==other.bp
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return DirSegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return DirSegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return DirSegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "DirSegLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class SegLine:	#line segmeny. senbun.
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = +self.dv.th
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp) or (self.ap==other.bp and self.bp==other.ap)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return SegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return SegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return SegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "SegLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class HalfLine:
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = +self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.th==other.th
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return HalfLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return HalfLine(self.ap-v, self.bp-v)
	def rotated(self,th):
		return HalfLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "HalfLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class Line:
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
		if not(bp is None) and not(th is None): self.setApBp(bp-Vector(d=1,th=th), bp)
		if ap.isLineLike: self.setApBp(ap.ap,ap.bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = +self.dv.th
	def __eq__(self,other):
		#return ( self.ap==other.ap or self.ap==other.bp or (self.ap-other.ap).isParaWith(other.dv) )	\
		#	and( self.bp==other.ap or self.bp==other.bp or (self.bp-other.bp).isParaWith(other.dv) )
		return self.ap.isOn(other) and self.bp.isOn(other)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return Line(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return Line(self.ap-v, self.bp-v)
	def rotated(self,th):
		return Line(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "Line(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class Circle:
	isLineLike=False
	def __init__(self,p,d):
		self.setPD(p,d)
	def setPD(self,p,d):
		self.p=+p
		self.d=Real(d)
	def __eq__(self,other):
		return self.p==other.p and self.d==other.d
	def __add__(self,v):
		return Circle(self.p+v, +self.d)
	def __sub__(self,v):
		return Circle(self.p-v, +self.d)
	def rotated(self,th):
		return Circle(self.p.rotated(th), +self.d)
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "Circle(p="+str(self.p)+", d="+str(self.d)+")"

class Triangle:
	isLineLike=False
	def __init__(self,ap,bp,cp):
		self.setApBpCp(ap,bp,cp)
	def setApBpCp(self,ap,bp,cp):
		self.ap=+ap
		self.bp=+bp
		self.cp=+cp
		self.calcFromApBpCp(ap, bp, cp)
	def calcFromApBpCp(self,ap,bp,cp):
		self.ae=SegLine(bp,cp)
		self.be=SegLine(cp,ap)
		self.ce=SegLine(ap,bp)
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp and self.cp==other.cp) \
			or (self.ap==other.bp and self.bp==other.cp and self.cp==other.ap) \
			or (self.ap==other.cp and self.bp==other.ap and self.cp==other.bp)
	def __add__(self,v):
		return Triangle(self.ap+v,self.bp+v,self.cp+v)
	def __sub__(self,v):
		return Triangle(self.ap-v,self.bp-v,self.cp-v)
	def rotated(self,th):
		return Triangle(self.ap.rotated(th),self.bp.rotated(th),self.cp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def area(self):
		return abs((self.ae).outprod(self.be))/2
	def gravityCenter(self):	#juushin
		return (self.ap+self.bp+self.cp)/3


def crossPoints(m,n):
	if m.isLineLike and n.isLineLike:
		c = m.dv.outprod(n.dv)
		if c==0: return []
		s = n.dv.outprod(m.ap-n.ap) / c
		t = m.dv.outprod(n.ap-m.ap) / c
		if (     ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=s<=1)	\
			or   (isinstance(m,HalfLine) and 0<=s)									\
			or   (isinstance(m,Line))												\
		   )and( ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=t<=1)	\
			or   (isinstance(m,HalfLine) and 0<=t)									\
			or   (isinstance(m,Line))												\
			):
			return [m.ap+m.dv*s]
		else:
			return []
	elif m.isLineLike and isinstance(n,Circle):
		re=[]
		l=perpendicular(n.p, m)
		if l.bp.isOn(n):
			p=+l.bp
			if p.isOn(m): re.append(p)
			return re
		if l.bp.isOut(n):
			return re
		if l.bp.isIn(n):
			r=sqrt(n.d**2-l.d**2)
			p1 = l.bp+Vector(d=r,th=m.th)
			p2 = l.bp-Vector(d=r,th=m.th)
			if p1.isOn(m): re.append(p1)
			if p2.isOn(m): re.append(p2)
			return re
	elif isinstance(n,Circle) and m.isLineLike:
		return crossPoints(n, m)
	elif isinstance(m,Circle) and isinstance(n,Circle):
		d = abs(m.p-n.p)
		if d==0 and m.d==n.d:	#itchi
			return []
		if d== m.d-n.d:			#naisetsu(n in m)
			return [(n.p*m.d-m.p*n.d)/(m.d-n.d)]
		if d < m.d-n.d:			#naihou(n in m)
			return []
		if d== n.d-m.d:			#naisetsu(m in n)
			return [(m.p*n.d-n.p*m.d)/(n.d-m.d)]
		if d < n.d-m.d:			#naihou(n in m)
			return []
		if d== m.d+n.d:			#gaisetsu
			return [(m.p*n.d+n.p*m.d)/(m.d+n.d)]
		if d > m.d+n.d:			#hanareteru
			return []
		if d < m.d+n.d:
			x = (d**2+m.d**2-n.d**2)/(2*d)
			y = sqrt(m.d**2-x**2)
			th = (n.p-m.p).th
			v1 = Vector(x,y)
			v1 = v1.rotated(th)
			v2 = Vector(x,-y)
			v2 = v2.rotated(th)
			return [m.p+v1, m.p+v2]

def perpendicular(p,m):
	ap=p
	th=m.th+pi/2
	bp=crossPoints(Line(m.ap,m.bp), Line(ap=ap,th=th))[0]
	re = DirSegLine(ap,bp)
	if not re.th.isParaWith(th): re.th=th
	return re

class Ufo:
	def __init__(self,px,py,d,vd,i):
		p=Vector(px,py)
		self.p=p
		self.d=Real(d)
		self.c=Circle(p,d)
		self.v=-p.e()*Real(vd)
		self.i=i
	def move(self): #genten toottaka wo kaesu
		re=False
		if(abs(self.p)<=abs(self.v)): re=True
		self.p=self.p+self.v
		self.c=self.c+self.v
		return re

class Laser:
	def __init__(self,u,ignArea):	#yuukou hanni R ijou de u ni mukatte utu
		self.line = HalfLine(ap=u.p.e()*(ignArea.d), th=u.p.th)
		self.ignArea = ignArea
	def hit(self,u):
		ps = crossPoints(self.line, u.c)
		#ps = filter(lambda p: p.isOut(ignArea), ps)
		return len(ps)!=0

while True:
	R,ul = tuple(map(int,raw_input().split()))
	if(R==0 and ul==0): break
	ignArea = Circle(Vector(0,0),R)
	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:
		#print "ufos moved"
		rus=[] #us to be removed
		for u in us:
			passed = u.move()
			if passed or u.p.isIn(ignArea):
				re+=1
				rus.append(u)
		for u in rus:
			#print u.i, "removed due to it invaded inside"
			us.remove(u)

		if len(us)==0:
			break

		neu=Ufo(inf,inf,1,1,1000)
		for u in us:
			if abs(u.p)<abs(neu.p):
				neu=u
		laser = Laser(neu,ignArea)

		rus=[]
		for u in us:
			if laser.hit(u):
				#print u.i, "removed due to laser hit"
				rus.append(u)
		for u in rus:
			us.remove(u)

		if len(us)==0:
			break

	print re

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.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()

		for u in us[:]:
			if u.pd<=R:
				re+=1
				us.remove(u)
		if len(us)==0: break

		neu = Ufo(2000,2000,1,1,1)
		for u in us:
			if u.pd < neu.pd:
				neu=u
		laserex=neu.ex
		laserey=neu.ey

		for u in us[:]:
			d = u.pd*abs(laserex*u.ey-laserey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*abs(laserex*u.ex+laserey*u.ey)+sqrt(u.d**2-d**2) > R:
					us.remove(u)
		if len(us)==0: break

	print re

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.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()

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

		neu = Ufo(2000,2000,1,1,1)
		for u in us:
			if u.pd < neu.pd:
				neu=u
		laserex=neu.ex
		laserey=neu.ey

		for u in us[:]:
			d = u.pd*abs(laserex*u.ey-laserey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*abs(laserex*u.ex+laserey*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:
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"
		laserex=neu.ex
		laserey=neu.ey

		for u in us[:]:
			d = u.pd*abs(laserex*u.ey-laserey*u.ex)	#u kara laser ni orosita suisen no nagasa
			if d<u.d:
				if u.pd*abs(laserex*u.ex+laserey*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