Задача F. Велогонка

Автор:Жюри ROI-2011   Ограничение времени:2 сек
Входной файл:bicycle.in   Ограничение памяти:256 Мб
Выходной файл:bicycle.out  
Максимальный балл:100  

Условие

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на x1, x2, …, xn метров (n – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью v1, v2, …, vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

Репортёр, освещающий ход соревнований, хочет определить момент времени, в который расстояние между лидирующим в гонке велосипедистом и замыкающим гонку велосипедистом станет минимальным, чтобы с вертолёта сфотографировать сразу всех участников велогонки.

Требуется написать программу, которая по заданному количеству велосипедистов n, заданным начальным положениям велосипедистов x1, x2, …, xn и их скоростям v1, v2, …, vn, вычислит момент времени t, в который расстояние l между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число n – количество велосипедистов.

В последующих n строках указаны по два целых числа: xi – расстояние от старта до i-го велосипедиста в начальный момент времени (0 ≤ xi ≤ 107) и vi – его скорость (0 ≤ vi ≤ 107).

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

В выходной файл необходимо вывести два вещественных числа: t – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, l – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более 10 − 6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x − y| / max(1, |y|) не превышает 10 − 6.

Ограничения

2 ≤ n ≤ 105

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

Входной файл (bicycle.in) Выходной файл (bicycle.out)
1
3
0 40
30 10
40 30
1 30
2
5
90 100
100 70
100 70
110 60
120 35
0.5 5.000000000000

0.090s 0.015s 13