← 返回题目列表

Codeforces · 1936/F

F. 大结局:圆圈

中文机器翻译题面 查看原题

飞机上有 $$$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}$$$ 时,您的答案才会被接受。

输入

第一行包含一个整数 $$$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$$$ 圆内。

输出

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

示例

输入 #1

4
1 1 3
-1 1 3
1 -1 2
-1 -1 2

输出 #1

0.0000000000000000 -0.7637626158259733 0.9724747683480533

输入 #2

4
41580 -23621 95642
-41580 -23621 95642
0 47821 95642
0 0 109750

输出 #2

0.0000000000000000 0.0000000000000000 47821.0000000000000000

注意

下面给出了描述第一个测试用例的二维图。输出圆 $$$C$$$ 用蓝色虚线表示。

下面给出了描述第二个测试用例的二维图。输出圆 $$$C$$$ 用蓝色虚线表示。