CF1936F.Grand Finale: Circles

You are given $n$ circles on the plane. The $i$-th of these circles is given by a tuple of integers $(x_i, y_i, r_i)$, where $(x_i, y_i)$ are the coordinates of its center, and $r_i$ is the radius of the circle.

Please find a circle $C$ which meets the following conditions:

• $C$ is contained inside all $n$ circles given in the input.
• Among all circles $C$ that meet the first condition, the radius of the circle is maximum.

Let the largest suitable circle have the radius of $a$.

Your output $C$, described as $(x,y,r)$, will be accepted if it meets the following conditions:

• For each $i$, $\sqrt{(x_i-x)^2+(y_i-y)^2}+ r \le r_i+\max(a,1)\cdot 10^{-7}$.
• The absolute or relative error of $r$ does not exceed $10^{-7}$. Formally, your answer is accepted if and only if $\frac{\left|r - a\right|}{\max(1, a)} \le 10^{-7}$.

平面上给出 $n$ 个圆。其中第 $i$ 个圆由整数三元组 $(x_i, y_i, r_i)$ 给出，$(x_i, y_i)$ 表示其圆心坐标，$r_i$ 表示其半径。

请找出一个圆 $C$，使其满足以下条件：

• $C$ 完全包含于输入给出的全部 $n$ 个圆内；
• 在所有满足第一条条件的圆中，$C$ 的半径最大。

设满足条件的最大圆的半径为 $a$。

你输出的圆 $C$（以三元组 $(x, y, r)$ 描述）若满足以下条件，则视为正确：

• 对每个 $i$，有 $\sqrt{(x_i-x)^2+(y_i-y)^2}+ r \le r_i+\max(a,1)\cdot 10^{-7}$；
• $r$ 的绝对误差或相对误差不超过 $10^{-7}$。形式化地，当且仅当 $\frac{\left|r - a\right|}{\max(1, a)} \le 10^{-7}$ 时，你的答案被接受。

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of circles.

The $i$-th of the following $n$ lines contains three integers $x_i$, $y_i$, $r_i$ ($-10^6 \le x_i,y_i \le 10^6$, $1 \le r_i \le 2 \cdot 10^6$).

It is guaranteed that there is a circle with a radius of at least $10^{-6}$ which is contained inside all $n$ circles.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 圆的个数。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$、$r_i$（$-10^6 \le x_i,y_i \le 10^6$，$1 \le r_i \le 2 \cdot 10^6$）。

保证存在一个半径至少为 $10^{-6}$ 的圆，它被包含在全部 $n$ 个圆的内部。

Output three real values, $x$, $y$, and $r$ — the coordinates of the center and the radius of the circle.

输出三个实数值 $x$、$y$ 和 $r$ —— 分别为圆心的坐标和圆的半径。

A two-dimensional plot depicting the first test case is given below. The output circle $C$ is dashed with blue lines.

A two-dimensional plot depicting the second test case is given below. The output circle $C$ is dashed with blue lines.

下面给出了第一个测试用例的二维示意图。输出圆 $C$ 以蓝色虚线绘制。

下面给出了第二个测试用例的二维示意图。输出圆 $C$ 以蓝色虚线绘制。