In [1]:

    

"""
Archery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery
"""


    

    
Out[1]:





'\nArchery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery\n'

In [7]:

    

# 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


    

In [8]:

    

isQ(1,(1,1,0,0))


    

    
Out[8]:





True

In [57]:

    

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


    

In [16]:

    

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

In [58]:

    

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

In [24]:

    

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

In [ ]: