Dome of the Circus

Time limit1sMemory limit128 MB

Summary

Given 3D points, find the minimum-volume cone with apex on the z-axis and base on the ground plane that contains all points, then output its height and radius.

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

Problem

A travelling circus needs to design the dome for its aerial performances. Various rigs, supports, and anchors are installed in the air above the stage, and the dome must rise above the centre of the stage in the shape of a cone and cover all of them. Because the space under the dome must be air-conditioned, the dome should enclose the smallest possible volume.

You are given $n$ points in space. The point $(x_i, y_i, z_i)$ is the position of the $i$ -th object that must be covered, for $1 \le i \le n$ . The ground is the plane $z = 0$ , with positive $z$ pointing up, and the centre of the stage is the origin $(0, 0, 0)$ .

The tip of the dome is a point $(0, 0, h)$ with $h > 0$ . The dome is a cone whose base is the circle of radius $r$ centred at $(0, 0, 0)$ on the ground. Every given point must lie inside or on the surface of the cone. Among all such cones, find the one with the smallest volume.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10\,000$ ) — the number of points to cover. Each of the next $n$ lines contains three floating-point numbers $x_i$ , $y_i$ , and $z_i$ — the coordinates of the $i$ -th point. Every coordinate has absolute value at most $1000$ and at most two digits after the decimal point. Every $z_i$ is positive, and at least one point has a non-zero $x_i$ or $y_i$ .

Output

Print two numbers $h$ and $r$ separated by a single space: the height and the base radius of the minimum-volume dome. Print each value rounded to exactly three digits after the decimal point (for example, 3.000). The optimal dome is unique, so both values are uniquely determined.

Examples5

Example 1
Input
```
1
1.00 0.00 1.00
```
Expected output
```
3.000 1.500
```

Example 2

Input

2
1.00 0.00 1.00
0.00 1.50 0.50

Expected output

2.000 2.000

Example 3

Input

3
1.00 0.00 1.00
0.00 1.50 0.50
-0.50 -0.50 1.00

Expected output

2.000 2.000

Example 4
Input
```
1
2.00 0.00 2.00
```
Expected output
```
6.000 3.000
```
Example 5
Input
```
1
3.00 4.00 5.00
```
Expected output
```
15.000 7.500
```