제출 #954001

#제출 시각아이디문제언어결과실행 시간메모리
954001ayeshz원 고르기 (APIO18_circle_selection)Pypy 3
7 / 100
3060 ms104256 KiB
# 11:10 -> 11:33
import math

n = int(input())
circles = []
for _ in range(n):
    x, y, r = [int(a) for a in input().split()]
    circles.append([x,y,r]) # r=-1 will indicate that the circle is removed
    

n_removed = 0
removing_list = [-1]*n
while n_removed < n:
    r_max = 0
    r_max_idx = -1
    for i in range(len(circles)):
        circle = circles[i]
        if circle[2] > r_max:
            r_max = circle[2]
            r_max_idx  = i
    if r_max_idx == -1:
        break
    x_max = circles[r_max_idx][0]
    y_max = circles[r_max_idx][1]
    r_max = circles[r_max_idx][2]
    
    for i in range(len(circles)):
        circle = circles[i]
        if circle[2] < 1:
            continue
        dis = (circle[0] - x_max)**2 + (circle[1] - y_max)**2
        if dis <= (r_max+circle[2])**2:
            removing_list[i] = str(r_max_idx + 1)
            circle[2] = -1
            n_removed += 1
            
    #n_removed += 1
    circles[r_max_idx][2] = -1
    
print(' '.join(removing_list))
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...