Задача G. Пузыри на плоскости ≡

Условие

Рассмотрим множество непрерывно растущих пузырей, расположенных на плоскости. Каждый такой пузырь представляет собой круг, заданный координатами своего центра (x_i, y_i) и радиальной скоростью v_i, указывающей приращение его радиуса за единицу времени.

Известно, что рост отдельно взятого пузыря будет остановлен, как только он достигнет границы любого другого. При этом полагается, что в начальный момент времени (t = 0) радиусы всех пузырей равны нулю.

Требуется определить наиболее ранний момент времени, когда ни один из пузырей больше не сможет продолжать свой рост.

В свою очередь, для каждого такого пузыря следует указать максимально возможный радиус, которого он успеет достичь.

Формат входного файла

Во входном файле "input.txt" хранится натуральное число n, указывающее количество пузырей.
Далее следует набор из 3 × n вещественных чисел: x_i, y_i, v_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать время окончания роста всех таких пузырей
и значения их радиусов r_i в конечный момент времени.
Все значения должны быть записаны с точностью до 5-го знака после запятой.

Ограничения

 − 100 ≤ (x_i, y_i) ≤ 100, 0 ≤ v_i ≤ 20,

2 ≤ n ≤ 500

Примеры тестов

 5
 3.05780 -1.53000  2.92010
-9.05000 -2.37000  1.57000
-7.01400  1.09000  3.06000
 4.05600  8.41000  2.24000
-3.89000 -3.57000  1.00000

2.05182
5.39393
1.36132
2.65327
4.59607
1.84717

 5
-1.15000  0.96070  3.01280
 9.38000 -2.37000  1.57000
-1.15000  0.96070  3.06000
 6.43010  4.23080  0.00000
 3.89000 -3.57000  2.00000

1.57412
0.00000
2.47137
0.00000
0.00000
3.14825