飞机上有 $$$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$$$ 用蓝色虚线表示。