32573번 - Cowpproximation 스페셜 저지다국어

문제

There are cows in a 2ドル$ by 2ドル$ kilometer field. The cows want to have a group meeting, and all of them must attend! It is up to you to plan the meeting to take place as soon as possible.

To model this problem, we approximate each cow as a circle, and for our purposes, there are no collisions — cows can pass through each other freely.

The $i$-th cow is represented by its initial position $(x_i , y_i)$ and its radius $r_i,ドル all distances are measured in meters. You can tell each cow to travel in any direction from its initial position at a constant speed from 0ドル$ to 1ドル$ meter per second. The meeting takes place as soon as all cows occupy the same point in the plane, i.e., there exists a point contained within all circles representing the cows. Find the minimum time in seconds required for the cows to meet.

입력

The first input line contains a single integer $N$ (1ドル ≤ N ≤ 10^3$), representing the number of cows. Each of the following $N$ lines contains three space separated integers $x_i,ドル $y_i,ドル $r_i,ドル describing a cow, where $-10^3 ≤ x_i , y_i ≤ 10^3$ and 1ドル ≤ r_i ≤ 10^3$.

출력

Output the minimum time $T$ in seconds after which all the cows meet. Your answer will be considered correct if it has an absolute or relative error at most 10ドル^{-5}$. Formally, let $T_{OPT}$ be the optimal value. Then your answer is considered correct if either $|T - T_{OPT}| ≤ 10^{-5}$ or $\left| \frac{T - T_{OPT}}{\max\{1,T_{OPT}\}} \right| ≤ 10^{-5}$ holds.

제한

힌트