Задача 102933
|
Название задачи: Прямоугольники . |
 |
Условие
На ось Ox плоскости Oxy положили N прямоугольников. Требуется найти координаты вершин ломаной, огибающей это множество прямоугольников сверху (см. рис.).Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100). Далее следуют N строк, в каждой из которых записана тройка вещественных чисел, описывающих очередной из прямоугольников. Первое из них задает абсциссу левого нижнего угла прямоугольника, а остальные два – его длину и высоту.
Выходные данные
В первую строку выходного файла выведите количество вершин искомой ломаной. Далее укажите сами вершины в порядке неубывания абсциссы. Каждая вершина задается своими координатами, записанными через пробел в отдельной строке выходного файла. Никакие два звена ломаной не должны лежать на одной прямой.
Пример входного файла
2
0 4 2
2 4 5
Пример выходного файла
6
0 0
0 2
2 2
2 5
6 5
6 0
Решение
Скачать архив тестов и решенийРассмотрим абсциссы всех вершин всех прямоугольников и отсортируем их по возрастанию. В результате ось Ox разобьется на отрезки. Очевидно, что ломаная может менять высоту, на которой идут ее горизонтальные звенья, только в концах этих отрезков, а между ними она идет на постоянной высоте. Определим эти высоты. Возьмем для этого середину каждого отрезка и рассмотрим все прямоугольники, ее покрывающие. Нужно выбрать максимальную из их высот.
Тем самым, мы получили набор горизонтальных звеньев нашей ломаной.
Вертикальные звенья возникают там, где ломаная меняет высоту, на которой
она идет.
Упражнение
Придумайте решение этой задачи со временем работы O(N log N). Используйте
для этого структуру данных, называемую очередью с приоритетами [Ахо 79,
п. 4.9].
