На плоскости даны \(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}\).
Выходные данные
Выведите три числа \(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
|