Submission #953652

#	Time	Username	Problem	Language	Result	Execution time	Memory
953652		ayeshz	Circle selection (APIO18_circle_selection)	Pypy 3	7 / 100	3086 ms	98612 KiB

circle_selection

n = int(input())
from math import sqrt
def intersect(x1,y1,r1,x2,y2,r2):
    dist = sqrt(pow(x1-x2,2) + pow(y1-y2,2))
    if dist <= r1 + r2:
        return True
    return False
circles = []
for i in range(n):
    temp = tuple(map(int,input().split()))
    circles.append((i+1,temp[0],temp[1],temp[2]))
ais = [-1] * n
circles.sort(key=lambda x: x[3],reverse=True)
for i in range(n):
    if ais[circles[i][0]-1] != -1:
        continue
    x, y, r = circles[i][1],circles[i][2],circles[i][3]
    ais[circles[i][0]-1] = circles[i][0]
    # this is largest circle, find intersecting circles
    for j in range(i+1,n):
        if ais[circles[j][0]-1] != -1:
            continue
        if intersect(x,y,r,circles[j][1],circles[j][2],circles[j][3]):
            ais[circles[j][0]-1] = circles[i][0]
#print(ais)
print(' '.join(map(str,ais)))

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13