Олимпиадный тренинг

Задача . 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\)) — количество кругов.

В \(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\) — координаты центра и радиус круга.

Примечание

Ниже представлена координатная плоскость, описывающая первый набор входных данных. Найденный круг \(C\) заштрихован синими линиями.

Ниже представлена координатная плоскость, описывающая второй набор входных данных. Найденный круг \(C\) заштрихован синими линиями.


Примеры
№Входные данныеВыходные данные
1
4
1 1 3
-1 1 3
1 -1 2
-1 -1 2
0.0000000000000000 -0.7637626158259733 0.9724747683480533
2
4
41580 -23621 95642
-41580 -23621 95642
0 47821 95642
0 0 109750
0.0000000000000000 0.0000000000000000 47821.0000000000000000
Статистика успешных решений по компиляторам
 Кол-во
С++3