시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 226 | 37 | 28 | 15.730% |
Given n circles c1, c2, . . . , cn on a flat Cartesian plane. We attempt to do the following:
We say ci is eliminated by cj if cj is the chosen circle in the iteration where ci is removed. For each circle, find out the circle by which it is eliminated.
The first line contains an integer n, denoting the number of circles (1 ≤ n ≤ 3 · 105). Each of the next n lines contains three integers xi, yi, ri, representing the x-coordinate, the y-coordinate, and the radius of the circle ci (−109 ≤ xi, yi ≤ 109, 1 ≤ ri ≤ 109).
Output n integers a1, a2, . . . , an in the first line, where ai means that ci is eliminated by cai.
11 9 9 2 13 2 1 11 8 2 3 3 2 3 12 1 12 14 1 9 8 5 2 8 2 5 2 1 14 4 2 14 14 1
7 2 7 4 5 6 7 7 4 7 6
The picture in the statements illustrates the first example.