"""
Archery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery
"""
'\nArchery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery\n'
# Enter your code here. Read input from STDIN. Print output to STDOUT
# radii = [1,2,3,4]
def isQ(r,line):
x1,y1,x2,y2 = line
if y1 == y2 and x1 == x2:
#print "Arrow of zero length."
return False
if x1 == x2:
y_sqr = (r**2 - c**2)
if y_sqr < 0:
#print "No intersection"
return False
y = y_sqr**0.5
if (y-y1)*(y-y2) <= 0 and (-y-y1)*(-y-y2) > 0:
#print "Exactly one intersection with circle"
return True
if (-y-y1)*(-y-y2) <= 0 and (y-y1)*(y-y2) > 0:
#print "Exactly one intersection with circle"
return True
m = (y1-y2)/(1.0*(x1-x2))
c = y1 -m*x1
a = (m**2+1)
b = 2*m*c
d = c**2 - r**2
#print "Parameters (m,c,a,b,d): ", m,c,a,b,d
sqrt_t = b**2 - 4*a*d
#print "SQRT_T", sqrt_t
if sqrt_t < 0:
#print "No intersection"
return False
sqrt_t = sqrt_t ** 0.5
#print "SQRT_T", sqrt_t
x = (-b + sqrt_t)/(2*a)
y = m*x + c
count_p = 0
#print "Intersection point: ",x , y
if (y-y1)*(y-y2) <= 0 and (x-x1)*(x-x2) <=0:
count_p += 1
x = (-b - sqrt_t)/(2*a)
y = m*x + c
#print "Intersection point: ",x , y
if (y-y1)*(y-y2) <= 0 and (x-x1)*(x-x2) <=0:
count_p += 1
if count_p != 1:
#print "More than one intersection with circle", count_p
return False
return True
isQ(1,(1,1,0,0))
True
def calcQ(radii, lines):
count = 0
for r in radii:
r = r**2
for line in lines:
x1,y1,x2,y2 = line
min_r = min(((x1**2)+(y1**2)), ((x2**2)+(y2**2)))
if min_r > r:
print "All points beyond this are discarded", r, line
break
max_r = max(((x1**2)+(y1**2)), ((x2**2)+(y2**2)))
if r!= min_r and r != max_r and (r-min_r)*(r-max_r) > 0:
print "Outside range: ", r, min_r, max_r, line
continue
count += 1
#if isQ(r,line):
#count += 1
return count
n = int(input())
radii = [int(k) for k in raw_input().split()]
lines = []
n = int(input())
for i in range(n):
lines.append([int(k) for k in raw_input().split()])
print calcQ(radii,lines)
4 1 2 3 4 3 1 -1 4 -3 2 1 1 2 1 -2 3 -4 3
n = int(input())
radii = [int(k) for k in raw_input().split()]
radii = sorted(radii)
#print radii
lines = []
n = int(input())
for i in range(n):
lines.append([int(k) for k in raw_input().split()])
lines.sort(key=lambda x: min(((x[0]**2)+(x[1]**2)), ((x[2]**2)+(x[3]**2))))
print lines
print calcQ(radii,lines)
4 1 2 3 4 3 1 -1 4 -3 2 1 1 2 1 -2 3 -4 [[1, -1, 4, -3], [2, 1, 1, 2], [1, -2, 3, -4]] All points beyond this are discarded 1 [1, -1, 4, -3] All points beyond this are discarded 4 [2, 1, 1, 2] Outside range: 9 5 5 [2, 1, 1, 2] Outside range: 16 5 5 [2, 1, 1, 2] 5
n = int(input())
radii = [int(k) for k in raw_input().split()]
radii = sorted(radii)
#print radii
lines = []
n = int(input())
for i in range(n):
lines.append([int(k) for k in raw_input().split()])
print calcQ(radii,lines)
4 1 2 3 4 3 1 -1 4 -3 2 1 1 2 1 -2 3 -4 Outside range: 1 [1, -1, 4, -3] Outside range: 1 [2, 1, 1, 2] Outside range: 2 [2, 1, 1, 2] Outside range: 3 [2, 1, 1, 2] Outside range: 4 [2, 1, 1, 2] Outside range: 1 [1, -2, 3, -4] Outside range: 2 [1, -2, 3, -4] Outside range: 3 [1, -2, 3, -4] Makes Q Outside range: 4 [1, -2, 3, -4] Makes Q 5