Кошелек или жизнь
Джонни с друзьями решили провести ночь Хэллоуина, собирая конфеты в домах своей деревни. Поскольку деревня слишком велика для одной группы для сбора конфет со всех домов последовательно, Джонни и его друзья решили разделиться, чтобы каждый из них пошел в разные дома, собрал там конфеты (или посеял хаос если жители не дадут конфет), и вернулся к заранее оговоренному месту встречи.
В деревне n домов, положение которых можно определить по их декартовым координатам на евклидовой плоскости. Банда Джонни также состоит из n людей (включая самого Джонни). Они решили распределить между собой конфеты после того, как все вернутся со своей добычей. Дома могут быть далеко, но Джонни заинтересован в том, чтобы съесть конфеты как можно скорее.
Помня, что из-за реакции некоторых сельских жителей на их гостеприимство местные власти могут разыскивать некоторых детей, они договорились закрепить место встречи у реки, протекающей через деревню, которая является линией y = 0. Обратите внимание, что по обе стороны реки могут быть дома, а некоторые дома могут быть плавучими домами (y = 0). Скорость ходьбы каждого ребенка 1 метр в секунду, и они могут двигаться в любом направлении на плоскости.
Ровно в полночь каждый ребенок постучит в дверь выбранного им дома, мгновенно заберет конфеты и вернется по кратчайшему маршруту к месту встречи. Сообщите Джонни, в какое время он сможет начать есть конфеты.
Входные данные
Каждый тест начинается со строки содержащей количество домов n (1 ≤ n ≤ 50000). Следующие n строк описывают положения домов. Каждая строка содержит два действительных числа x и y (-200 000 ≤ x, y ≤ 200 000) - координаты дома в метрах. Все дома имеют различные местоположения. После каждого теста расположена пустая строка. Строка с n = 0 означает конец входных данных и не обрабатывается.
Выходные данные
Для каждого теста выведите два числа в строке: координату x точки встречи на линии y = 0, минимизирующую время прибытия последнего ребенка, и это время само по себе (измеряется в секундах после полуночи). Числа выводить с 4 десятичными цифрами.