Задача E. Баба Яга летит в гости

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

Условие

В тридевятом царстве жила-была Баба Яга. А в тридесятом царстве жил-был Кощей Бессмертный. Однажды Баба Яга решила слетать в гости к Кощею в своей ступе.

Баба Яга будет лететь строго в плоскости, перпендикулярной земле. Пусть тридевятое царство, в котором живёт Баба Яга, находится в точке (x = a, y = 0), а тридесятое царство, в котором живёт Кощей Бессмертный, находится в точке (x = b, y = 0), a < b. Между этими царствами гористая местность. Профиль гор в плоскости полёта Бабы Яги задаётся ломаной с координатами вершин (x = xi, y = yi), i = 1, 2, ..., N, a = x1 < x2 < ... < xN = b, yi ≥ 0, y1 = yN = 0. Ступе будет сообщена некоторая начальная скорость, после чего она полетит в поле тяжести Земли по параболе (сопротивлением воздуха пренебрегаем). Баба Яга хочет попасть в точности в тридесятое царство, чтобы потом не пришлось идти пешком или запускать ступу ещё раз.

Баба Яга должна пролететь так, чтобы не врезаться в гору. Баба Яга страшно боится высоты, поэтому она хочет, чтобы максимальная высота, на которую она поднимется, была минимальной.

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

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

Входной файл содержит целое число N. Далее следуют N пар целых чисел xi yi.

Числа a и b определяются так: a = x1, b = xN.

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

Требуется вывести в выходной файл единственное вещественное число — минимально возможную максимальную высоту — с точностью до 4-х знаков после запятой.

Ограничения

3 ≤ N ≤ 1000

0 ≤ a = x1 < x2 < ... < xN = b ≤ 1000

0 ≤ yi ≤ 1000, y1 = yN = 0

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 0
2 1
3 0
1.0000
2
3
1 0
2 1
4 0
1.1250
3
4
2 0
3 9
4 5
6 0
12.0000

Разбор

Найдём множество парабол, которому принадлежит искомая парабола. Искомую параболу можно представить в виде y = h − c(x − (a + b)/2)2, где c — некоторая константа, h — максимальная высота. Найдём c из условия, что y обращается в ноль при x = a и при x = b.

h − c(a − (a + b)/2)2 = h − c(b − (a + b)/2)2 = 0, отсюда c = 4 h / (b − a)2.

Итак, искомую параболу будем искать в виде y = h[1 − 4(x − (a + b)/2)2 / (b − a)2].

Требуется найти минимальное h, при котором ломаная будет расположена не выше параболы. В силу выпуклости подграфика параболы (множества точек, лежащих ниже параболы) это условие эквивалентно условию, что все точки (xi, yi) расположены не выше параболы.

Для каждой отдельной точки (xi, yi) найдём h, при котором парабола проходит через эту точку. Среди всех полученных значений h выберем максимальное — это и будет ответ в задаче.

Для нахождения h решим уравнение

yi = h[1 − 4(xi − (a + b)/2)2 / (b − a)2].

Получим

h = yi / [1 − 4(xi − (a + b)/2)2 / (b − a)2].


0.147s 0.014s 15