<ПРЕД Задача:
СЛЕД>
Задачу решил 61 пользователь: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Дождь

Time limit = 5

Рассмотрим двумерную модель мира, в которой имеется только два измерения — высота и длина. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами (x0, y0), ..., (xN, yN), где x0 < x1 < ... < xN и yiyj, для любых ij. Слева в точке x1 и справа в точке xN рельеф ограничен вертикальными горами огромной высоты. Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф — это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы. Требуется найти максимальную глубину в образовавшихся после дождя водоемах.

Вход В первой строке входного файла расположены натуральное число N (0 ≤ N ≤ 100) и H — действительное число, заданное с тремя цифрами после десятичной точки (0 ≤ H ≤ 109). В последующих N+1 строках по два целых числа xi, yi: -10000 ≤ xi, yi ≤ 10000 (0 ≤ iN). Числа в строках разделены пробелами.

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

Вход#1
7 7.000
-5 10
-3 4
-1 6
1 -4
4 17
5 3
9 5
12 15
Выход#1
15.8446

Автор:
Всероссийская олимпиада школьников, Пермь
апрель 2002

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 34.204.176.125