Anchored Balloon

Time limit1sMemory limit128 MB

Summary

Find the greatest height a balloon tied to ground anchors by fixed-length ropes can reach while all ropes hold and none cross.

Level: Hard9 of 10
Topics: Geometry, Binary search, Math
Solved: No attempts yet

Problem

A balloon placed on the ground is connected to one or more anchors on the ground with ropes. Each rope is long enough to connect the balloon and its anchor, and no two ropes cross each other. Figure E-1 shows such a situation.

Figure E-1: A balloon and ropes on the ground

Now the balloon takes off. Find how high it rises while every rope connection holds. The anchors stay where they are. The lengths of the ropes and the positions of the anchors are given. The ropes have no weight, so a rope pulled in any direction straightens completely. The balloon may drift sideways as it rises, so its horizontal position is free. Figure E-2 shows the highest position of the balloon for the situation in Figure E-1.

Figure E-2: The highest position of the balloon

Input

The input consists of multiple datasets, each in the following format.

n
x1 y1 l1
...
xn yn ln

The first line of a dataset contains an integer $n$ ( $1 \le n \le 10$ ), the number of ropes. Each of the following $n$ lines contains three integers $x_i$ , $y_i$ , and $l_i$ , separated by a single space. $P_i = (x_i, y_i)$ is the position of the anchor holding the $i$ -th rope, and $l_i$ is the length of that rope. The values satisfy $-100 \le x_i \le 100$ , $-100 \le y_i \le 100$ , and $1 \le l_i \le 300$ . The balloon is initially placed at $(0, 0)$ on the ground. Ignore the size of the balloon and of the anchors.

If $i \ne j$ , then $P_i$ and $P_j$ are different positions. The distance between $P_i$ and $(0, 0)$ is at most $l_i - 1$ , so the balloon always rises at least $1$ unit high.

Figures E-1 and E-2 correspond to the first dataset of the visible test case.

A line containing a single $0$ marks the end of the input.

Output

For each dataset, print on one line the maximum height the balloon reaches, rounded to seven digits after the decimal point. Pad with zeros so that all seven digits are always printed. Print no other characters. Every answer in the test data is at least $10^{-9}$ away from a rounding boundary, so the rounding direction is never ambiguous.

Examples1

Example 1

Input

3
10 10 20
10 -10 20
-10 10 120
1
10 10 16
2
10 10 20
10 -10 20
2
100 0 101
-90 0 91
2
0 0 53
30 40 102
3
10 10 20
10 -10 20
-10 -10 20
3
1 5 13
5 -3 13
-3 -3 13
3
98 97 168
-82 -80 193
-99 -96 211
4
90 -100 160
-80 -80 150
90 80 150
80 80 245
4
85 -90 290
-80 -80 220
-85 90 145
85 90 170
5
0 0 4
3 0 5
-3 0 5
0 3 5
0 -3 5
10
95 -93 260
-86 96 211
91 90 177
-81 -80 124
-91 91 144
97 94 165
-90 -86 194
89 85 167
-93 -80 222
92 -84 218
0

Expected output

17.3205081
16.0000000
17.3205081
13.8011200
53.0000000
14.1421356
12.0000000
128.3928757
94.1879092
131.1240816
4.0000000
72.2251798