eolymp
bolt
Try our new interface for solving problems
Məsələlər

Дождик

Дождик

В НИИ метеорологии решили изучить процесс образования водоёмов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения - высоту и длину. В этой модели рельеф местности можно представить как \textbf{N}-звенную ломаную с вершинами (\textbf{x_0}, \textbf{y_0}), ..., (\textbf{x_N}, \textbf{y_N}), где \textbf{x_0} < \textbf{x_1} < ... < \textbf{x_N} и \textbf{y_i} ≠ \textbf{y_j}, для любых \textbf{i} < \textbf{j}. Слева в точке \textbf{x_0} и справа в точке \textbf{x_N} рельеф ограничен вертикальными горами огромной высоты. Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины \textbf{H}. Но поскольку рельеф - это ламанная, то вода стекает и скапливается в углублениях, образуя водоёмы. Требуется найти максимальную глубину в образовавшихся после дождя водоёмах. \InputFile В первой строке задано натуральное число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) и \textbf{H} - действительное число, заданное с тремя цифрами после десятичной точки (\textbf{0} ≤ \textbf{H} ≤ \textbf{10^9}). В последующих \textbf{N+1} строках - по два целых числа \textbf{x_i}, \textbf{y_i} (\textbf{-10000} ≤ \textbf{x_i},\textbf{y_i} ≤ \textbf{10000}, \textbf{0} ≤ \textbf{i} ≤ \textbf{N}). Числа в строках разделены пробелами. \OutputFile Выведите единственное число - искомую глубину с точностью до \textbf{4}-х знаков после десятичной точки.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
1 6.567
0 0
10 20
Çıxış verilənləri #1
16.207406