저 롤러들 좀 봐

면접 대비

시간 제한1초메모리 제한128 MB

요약

두 롤러의 중심 거리가 반지름의 합과 같을 때 맞닿는다. 원점에 있는 롤러에서 시작해 다른 롤러를 돌리지 않는 마지막 롤러까지 사슬을 따라가 그 좌표를 출력한다.

난이도: 보통10점 중 4점
유형: 그래프, DFS, 기하, 구현
정답자: 아직 제출이 없습니다

문제

윈치(winch)에는 커다란 강철판 위에 $N$ 개의 롤러가 놓여 있다. 동력을 처음 만들어 내는 구동 롤러(drive-roller)는 원점 $(0, 0)$ 에 있다. 이 구동 롤러가 다른 롤러 하나를 돌리고, 그 롤러가 또 다른 롤러를 돌리는 식으로 사슬(chain)처럼 힘이 전달되어 마지막 롤러까지 이어진다. 마지막 롤러란 다른 롤러에 의해 돌아가기는 하지만 어떤 롤러도 돌리지 않는 롤러이다.

두 롤러는 서로 바깥쪽에서 맞닿아 있을 때에만 힘을 전달한다. 즉, 두 롤러의 중심 사이의 거리가 두 반지름의 합과 같을 때 한 롤러가 다른 롤러를 돌린다. 롤러 $i$ 와 롤러 $j$ 에 대해 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} = r_i + r_j$ 이면 두 롤러는 맞닿아 있다.

각 롤러 $i$ 의 중심 좌표 $(x_i, y_i)$ 와 반지름 $r_i$ 가 주어진다. 사슬의 마지막 롤러, 즉 돌아가지만 다른 롤러를 돌리지 않는 롤러의 좌표를 구하여라. 구동 롤러를 제외한 모든 롤러는 정확히 하나의 다른 롤러에 의해 돌아간다.

$2 \le N \le 1080$
$-5000 \le x_i \le 5000$ , $-5000 \le y_i \le 5000$
$3 \le r_i \le 1024$

입력

첫째 줄: 정수 $N$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에는 롤러 $i$ 를 나타내는 세 정수 $x_i$ , $y_i$ , $r_i$ 가 공백으로 구분되어 주어진다.

출력

사슬의 마지막 롤러의 $x$ 좌표와 $y$ 좌표를 공백으로 구분하여 한 줄에 출력한다.

예제1

예제 1
입력
```
3
0 0 30
30 40 20
-15 100 55
```
예상 출력
```
-15 100
```