Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером X×Y метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось N круглых колонн, снести которые не представляется возможным.
Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.
Входные данные
В первой строке входных данных содержатся вещественные числа X и Y, 1 <= X, Y <= 10
4 . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (X, 0), (X, Y) и (0, Y).
Во второй строке задается число N (0 <= N <= 10) - количество колонн. Следующие N строк содержат параметры колонн - i-я строка содержит три вещественных числа X
i, Y
i и R
i - координаты центра и радиус i-й колонны (R
i <= X
i <= X-R
i, R
i <= Y
i <= Y-R
i, 0.1 <= R
i <= min(X / 2, Y / 2); для любых i ≠ j sqrt( (X
i - X
j)2 + (Y
i - Y
j)2 )>= R
i + Rj). Все вводимые числа разделены пробелами.
Выходные данные
Выведите три вещественных числа: X
F, Y
F и R
F - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.
Примеры
№ | Входные данные | Выходные данные |
1
|
10 10 0
|
5.000 5.000 5.000
|
2
|
1 1000 0
|
0.500 0.500 0.500
|
3
|
10 10 4 1 1 1 9 9 1 1 9 1 9 1 1
|
5.000 5.000 4.657
|