Oh Those Rollers

Interview

Time limit1sMemory limit128 MB

Summary

Rollers touch when the distance between centers equals the sum of radii. Starting from the roller at the origin, follow the chain to the roller that drives no other and print its coordinates.

Level: Medium4 of 10
Topics: Graph, DFS, Geometry, Implementation
Solved: No attempts yet

Problem

A winch has a large steel plate holding $N$ rollers. The drive-roller, the ultimate source of power, sits at the origin $(0, 0)$ . The drive-roller turns one other roller, that roller turns another, and so on, so power travels along a chain until the final roller is reached — a roller that is driven but drives no other roller.

Two rollers transmit power only when they touch on the outside: one roller drives another exactly when the distance between their centers equals the sum of their radii. That is, rollers $i$ and $j$ touch when $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} = r_i + r_j$ .

You are given the center coordinates $(x_i, y_i)$ and radius $r_i$ of every roller $i$ . Find the coordinates of the last roller in the chain (the roller that is driven but drives no other roller). Every roller except the drive-roller is driven by exactly one other roller.

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

Input

Line 1: a single integer $N$ .
Lines 2 to $N+1$ : line $i+1$ describes roller $i$ with three space-separated integers $x_i$ , $y_i$ , and $r_i$ .

Output

A single line with two space-separated integers: the $x$ and $y$ coordinates of the last roller in the chain of driven rollers.

Examples1

Example 1
Input
```
3
0 0 30
30 40 20
-15 100 55
```
Expected output
```
-15 100
```