| Codeforces Round 930 (Div. 1) |
|---|
| Закончено |
На плоскости даны $$$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$$$) — количество кругов.
В $$$i$$$-й из следующих $$$n$$$ строк содержится три целых числа $$$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$$$ — координаты центра и радиус круга.
4 1 1 3 -1 1 3 1 -1 2 -1 -1 2
0.0000000000000000 -0.7637626158259733 0.9724747683480533
4 41580 -23621 95642 -41580 -23621 95642 0 47821 95642 0 0 109750
0.0000000000000000 0.0000000000000000 47821.0000000000000000
Ниже представлена координатная плоскость, описывающая первый набор входных данных. Найденный круг $$$C$$$ заштрихован синими линиями.
Ниже представлена координатная плоскость, описывающая второй набор входных данных. Найденный круг $$$C$$$ заштрихован синими линиями.
