Cowpproximation

Time limit4sMemory limit1024 MB

Summary

Given N circles that move at speed up to 1, find the earliest time at which all circles share a common point. Binary search on time with a circle intersection check.

Level: Medium7 of 10
Topics: Binary search, Geometry, Intervals
Solved: No attempts yet

Statement

Cows live in a field that is 2 kilometers by 2 kilometers. They want to hold a group meeting, and every cow must attend. Your job is to plan the meeting so that it happens as early as possible.

Each cow is approximated as a circle. In this problem there are no collisions, so cows can pass through each other freely.

The $i$ -th cow is given by its initial position $(x_i, y_i)$ and its radius $r_i$ . All distances are in meters. Each cow can be told to travel in any direction from its initial position at a constant speed between 0 and 1 meter per second. The meeting starts the moment all cows occupy the same point, that is, when some point lies inside every circle at once. Find the minimum time, in seconds, that the cows need to meet.

Input

The first line contains a single integer $N$ ( $1 \le N \le 10^3$ ), the number of cows. Each of the next $N$ lines contains three space-separated integers $x_i$ , $y_i$ , and $r_i$ that describe one cow, where $-10^3 \le x_i, y_i \le 10^3$ and $1 \le r_i \le 10^3$ .

Output

Print the minimum time $T$ in seconds after which all cows meet. An answer is accepted if its absolute error or relative error is at most $10^{-5}$ .

Examples2

Example 1
Input
```
2
-10 3 2
10 3 4
```
Expected output
```
7.0000000
```
Example 2
Input
```
3
-4 -4 1
6 0 3
0 8 5
```
Expected output
```
3.7039181
```