Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Intersection of Circles

For given two circles $c1$ and $c2$, print

4

if they do not cross (there are 4 common tangent lines),

3

if they are circumscribed (there are 3 common tangent lines),

2

if they intersect (there are 2 common tangent lines),

1

if a circle is inscribed in another (there are 1 common tangent line),

0

if a circle includes another (there is no common tangent line).

Input

Coordinates and radii of $c1$ and $c2$ are given in the following format.

$c1x \; c1y \; c1r$ 

$c2x \; c2y \; c2r$

  $c1x$, $c1y$ and $c1r$ represent the center coordinate and radius of the first circle.
  $c2x$, $c2y$ and $c2r$ represent the center coordinate and radius of the second circle.
  All input values are given in integers.

Output

Print "4", "3", "2", "1" or "0" in a line.

Constraints

$-1,000 \leq c1x, c1y, c2x, c2y \leq 1,000$

$1 \leq c1r, c2r \leq 1,000$

$c1$ and $c2$ are different

Sample Input 1

1 1 1
6 2 2

Sample Output 1

4

Sample Input 2

1 2 1
4 2 2

Sample Output 2

3

Sample Input 3

1 2 1
3 2 2

Sample Output 3

2

Sample Input 4

0 0 1
1 0 2

Sample Output 4

1

Sample Input 5

0 0 1
0 0 2

Sample Output 5

0



Sample input:
1 1 1
6 2 2


Sample output:
4

Submission status: Runtime Error

Solution code:

cx1, cy1, r1 = map(float, raw_input().split())
cx2, cy2, r2 = map(float, raw_input().split())

import math
distance = math.sqrt( math.pow(cx1-cx2, 2) + math.pow(cy1-cy2, 2) )
rsum = r1 + r2
rmax = math.max(r1, r2)
rmin = math.min(r1, r2)

import sys
if distance > rsum:
  print(4)
elif abs(distance - rsum) < sys.float_info.epsilon:
  print(3)
else:
  if rmax < distance + rmin:
    print(2)
  elif abs(rmax - distance - rmin) < sys.float_info.epsilon:
    print(1)
  else:
    print(0)

Submission status: Runtime Error

Solution code:
# Single Source Shortest Path
class node():
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost

infty = 999999999
dict_c = {}
[vertex, edge, r] = list(map(int, input("").split()))
root_c = [node(r, 0)]
final_c = [infty for i in range(vertex)]
final_c[r] = 0

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    if e1 == r:
        root_c.append(node(e2, c))
        final_c[e2] = c
    else:
        dict_c[(e1, e2)] = c

def min_heap(i):
    global root_c
    l = 2*i
    r = 2*i + 1
    if l <= len(root_c) - 1 and root_c[l].cost <= root_c[i].cost:
        if root_c[l].cost < root_c[i].cost:
            min = l
        elif root_c[l].v < root_c[i].v:
            min = l
        else:
            min = i
    else:
        min = i
    if r <= len(root_c) - 1 and root_c[r].cost <= root_c[min].cost:
        if root_c[r].cost < root_c[min].cost:
            min = r
        elif root_c[r].v < root_c[min].v:
            min = r
        #else:

    if min != i:
        root_c[i], root_c[min] = root_c[min], root_c[i]
        min_heap(min)

def build_min_heap():
    global root_c
    length = len(root_c) - 1
    for i in range(int(length/2), 0, -1):
        min_heap(i)

def extract_min():
    global root_c
    min = root_c[1]

    #print("min_cost  ", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost, root_c[7].cost)
    #print("min_vertex", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v, root_c[7].v)

    root_c[1] = root_c[len(root_c) - 1]

    #print("1: ",root_c[1].cost, root_c[1].v)

    del root_c[len(root_c) - 1]
    min_heap(1)

    #print("min_cost  2", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost)
    #print("min_vertex2", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v)
    #print("length: ",len(root_c))

    return min

def decrease_key(i, c):
    global root_c
    root_c[i].cost = c
    while i > 1 and root_c[int(i/2)].cost >= root_c[i].cost:
        if root_c[int(i/2)].cost > root_c[i].cost:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        elif root_c[int(i/2)].v > root_c[i].v:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        else:
            root_c[int(i/2)], root_c[i] = root_c[int(i/2)], root_c[i]
        i = int(i/2)

def min_insert(v, c):
    global infty, root_c
    for i in range(1, len(root_c)):
        if root_c[i].v == v:
            decrease_key(i,c)
            return

    root_c.append(node(v, infty))
    decrease_key(len(root_c) - 1, c)

def Dijkstra(root, n):

    count = 1

    global infty, dict_c, root_c, final_c
    label = [i for i in range(n)]

    #print(count, label[root], final_c[label[root]])
    count += 1

    del label[root]

    while len(label) != 0:
        if len(root_c) > 1:
            min_node = extract_min()
        else:
            break

        for i in range(len(label)):
            if min_node.v == label[i]:
                delete_label = i
                continue

            if ((min_node.v, label[i]) in dict_c.keys()) == True:
                if final_c[label[i]] > final_c[min_node.v] + dict_c[(min_node.v, label[i])]:
                    final_c[label[i]] = final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                    min_insert(label[i], final_c[label[i]])

        #print(count, label[delete_label], final_c[label[delete_label]])
        count += 1

        del label[delete_label]

build_min_heap()

'''
print("root_c :")
for i in range(len(root_c)):
    print(root_c[i].cost)
print("\n")
'''

Dijkstra(r, vertex)

#print("\n")

for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Submission status: Runtime Error

Solution code:
c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

s = c1r + c2r

if d > s:
    print 4
else if d == c:
    print 3
else if d > 2*s:
    print 2
else if d == 2*s:
    print 1
else:
    print 0

Submission status: Runtime Error

Solution code:
c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

s = c1r + c2r

if d > s:
    print(4)
else if d == c:
    print(3)
else if d > 2*s:
    print(2)
else if d == 2*s:
    print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

s = c1r + c2r

if d > s:
    print(4)
elif d == c:
    print(3)
elif d > 2*s:
    print(2)
elif d == 2*s:
    print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

s = c1r + c2r

if d > s:
    print(4)
elif d == c:
    print(3)
elif d > 2*s:
    print(2)
elif d == 2*s:
    print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

if d > c1r + c2r:
    print(4)
elif d == c1r + c2r:
    print(3)
elif d > s/2:
    print(2)
elif d == s/2:
    print(1)
else:
    print(0)

Submission status: Runtime Error

Solution code:



nv,ne = [int(i) for i in input().split()]

g = []

for i in range(nv):
    g.append([])

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

done = []

f = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for s in g[index]:

        if s == 0:
            f = 1
            return
        put_forword(s)

put_forword(0)

print(f)

Submission status: Runtime Error

Solution code:

nv,ne = [int(i) for i in input().split()]

g = []

for i in range(nv):
    g.append([])

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

done = []

f = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for i in g[index]:

        if i == 0:
            f = 1
            return
        put_forword(i)

put_forword(0)

print(f)

Submission status: Runtime Error

Solution code:

nv,ne = [int(i) for i in input().split()]

g = [[] for i in range(nv)]

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

visited = [False for i in range(nv)]
f = 0

def pursue_from(index):
    global f


    if visited[index]:
        return

    visited[index] = True

    for next_index in g[index]:

        if next_index == 0:
            f = 1
            return
        pursue_from(next_index)

pursue_from(0)

print(f)