Задача E. Сухой фотограф

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

В некотором городе имеется достопримечательность - прямоугольная площадь размером X на Y метров, на которой работают N фонтанов. Турист желает посетить эту площадь и сделать несколько фотографий. Однако если при фотографировании находиться от какого-либо из фонтанов на расстоянии меньше R метров, фотоаппарат может быть поврежден брызгами воды. Помогите фотографу найти безопасную точку съёмки. Требуется по координатам фонтанов определить точку на площади, удалённую от каждого из них не менее чем на R метров, или определить, что такой точки не существует. Если таких точек более одной, вывести любую из них. Обратите внимание, что стоять в точности на границе окружности или прямоугольника разрешено.

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

В первой строке входного файла содержатся числа X Y N R, в каждой из следующих N строк - координаты xi yi i-го фонтана. Числа X Y R во входном файле — вещественные.

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

В выходном файле должны, содержаться два вещественных числа - координаты сухой точки. Если такой точки не существует, следует вывести значения -1 -1. Проверка результатов будет осуществляться путём подстановки координат точки в неравенства, задающие внутренность каждого круга. Эти вычисления будут производиться с использованием вещественных чисел двойной точности (double).

Ограничения

1 <= N <= 100, 1 <= X, Y, R <= 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 100 4 50
0 0
100 0
0 100
100 100
50 50

0.024s 0.006s 15