Задача 55: Дождик (XIV Всероссийская
олимпиада по информатике)
В НИИ метеорологии решили изучить процесс образования водоемов на
различных рельефах местности во время дождя. Ввиду сложности
реальной задачи была создана двумерная модель, в которой местность
имеет только два измерения - высоту и длину. В этой модели рельеф
местности можно представить как N-звенную ломаную c вершинами
(x0, y0), ..., (xN, yN), где x0 < x1 < ... < xN и yi <> yj, для
любых i <> j. Слева в точке x0 и справа в точке xN рельеф ограничен
вертикальными горами огромной высоты.
Если бы рельеф был горизонтальным, то после дождя вся местность
покрылась бы слоем воды глубины H. Но поскольку рельеф - это
ломаная, то вода стекает и скапливается в углублениях, образуя
водоемы.
Требуется найти максимальную глубину в образовавшихся после дождя
водоемах.
Входные данные
В первой строке файла rain.in расположены натуральное число N
(1 <= N <= 100) и H - действительное число, заданное с тремя цифрами
после десятичной точки (0 <= H <= 10 в 9 степени). В последующих N + 1
строках - по два целых числа xi, yi: -10000 <= xi, yi <= 10000
(0 <= i <= N).
Числа в строках разделены пробелами.
Выходные данные
Выходной файл rain.out должен содержать единственное число -
искомую глубину с точностью до 4-х знаков после десятичной точки.
Пример
Входной файл rain.in
7 7.000
-5 10
-3 4
-1 6
1 -4
4 17
5 3
9 5
12 15
Выходной файл rain.out
15.8446
Решение: предоставлено С.В. Густокашиным
Начнем с того, что добавим две крайних точки. Координата X первой
точки совпадет с координатой x0, координата X последней - с
координатой xN. Координаты Y дополнительных точек зададим заведомо
больше возможной высоты слоя воды 100010000.
Запомним координаты Y и номера точек вершин и низин. Вершиной будем
считать ту точку, для которых координаты Y соседних точек слева и
справа меньше. Естественно за низину - ту, у которой координаты Y
соседних точек слева и справа больше.
Да, крайние, искусственно добавленные точки, причислим к вершинам.
Таким образом, у каждой низины будет две соседних вершины.
Рассчитаем "объем" (площадь) воды первоначально попадающей в низину
как разность координат X соседних вершин умноженную на H.
При этом, не обращаем внимание на возможный переизбыток воды -
наливаем "с горкой", потом разберемся с излишками.
Каждой вершине и низине поставим в соответствие "принадлежащие ей
трапеции" и рассчитаем их площади. Координаты трапеций для низин
начинаем с рассмотрения ближайших точек слева и справа. Естественно
первая трапеция - вырожденная и представляет собой треугольник.
Двигаемся до тех пор, перебирая координаты соседних точек слева и
справа и рассчитывая площади трапеций, пока одна из точек не
совпадет с координатой одной из вершин.
Координаты трапеций для вершин начинаем с рассмотрения ближайших
точек слева и справа, координаты Y которых больше координаты
вершины. Движемся от найденных точек влево и вправо до тех пор, пока
одна из точек не совпадет с координатой одной из вершин.
После таких действий все рабочее поле должно быть разбито на
трапеции, принадлежащие вершинам и низинам, и для каждой вершины и
низины будет рассчитана ее площадь как сумма площадей принадлежащих
ей трапеций.
А теперь закрутим бесконечный цикл "переливов" с двумя внутренними
циклами просмотра низин.
Первый цикл назовем "перелив влево" с просмотром низин справа
налево.
Если "объем" воды в низине больше ее собственного "объема" и
координата Y вершины слева меньше координаты Y вершины справа, то
убавляем "объем" воды, принадлежащей низине до ее собственного
"объема", а излишек добавляем низине слева.
По окончании "перелива влево" запускаем цикл "перелива вправо" с
"поглощением". Просмотр низин ведем слева направо. Условия перелива
похожи, если "объем" воды в низине больше ее собственного "объема" и
координата Y вершины справа меньше координаты Y вершины слева, то
убавляем "объем" воды, принадлежащей низине до ее собственного
"объема", а излишек добавляем низине справа. Если после перелива мы
видим, что координата Y правой вершины меньше координаты Y следующей
вершины справа, то производим "поглощение". Т.е. мы имеем случай,
когда две низины с вершиной между ними зажаты между более высокими
вершинами и обе низины полны.
Оставляем более глубокую низину, присваиваем ей "объем"
"поглощаемой" вершины, а объем воды в преобразившейся низине будет
составлять получившийся излишек при переливании. Набор трапеций
"поглощенной" вершины также будет принадлежать теперь оставшейся
низине. Устанавливаем флаг, что было "поглощение" чтобы после
продолжить бесконечный цикл "переливов".
Если при очередном проходе не будет ни одного "поглощения", значит
можно закончить бесконечный цикл "переливов" и приступать к
определению самой глубокой из оставшихся низин.
Для каждой низины у нас имеется координата Y, "объем" воды и набор
трапеций, принадлежащих низине. Для каждой трапеции, проверяем,
залита ли она полностью и если да, то просто добавляем ее высоту к
расчетной высоте воды в низине. Если трапеция залита не полностью,
рассчитываем высоту воды исходя из ее "объема" в трапеции.
После просмотра всех оставшихся низин определяем самую глубокую
низину.
При решении задачи возникла у меня небольшая проблема при расчете
высоты воды между искусственными крайними вершинами, поскольку это
вырожденная трапеция - прямоугольник. Выскочила ошибка "деление на
ноль", но, я думаю, зная об этом, вы правильно решите вырожденное
квадратное уравнение.
Разбор получился несколько затянутым, но задача того стоит, не
обессудьте.
А теперь, самое интересное: вначале предполагалась другая задача, в
которой координаты Y точек могут быть равны, а координаты X могут
быть произвольны, т.е. возможны гроты и равнины. Это бы сильно
усложнило задачу, но подождем олимпиаду следующего 2003 года.
Спасибо за терпение.
Далее
ð
