printРабочее место участника

printЗадачи

799. Линия горизонта

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вдоль прямой улицы стоят дома – прямоугольные параллелепипеды. Нужно найти линию горизонта – ломанную, "отделяющую дома от неба" при взгляде сбоку.
4208.png
Первая строка ввода содеджит одно целое число `N` `(2\ ≤\ N\ ≤\ 20000)` – количество домов, следующие `N` строк – по три целых числа (координата начала дома, его высота и длина). Все размеры и координаты – целые числа от 1 до `10^9`.
Вывод должен содержать описания отдельных горизонтальных фрагментов линиии горизонта – тройки вида начало, высота, конец. Линия горизонта левее самого левого и правее самого правого дома не описывается. В результатах не должно быть перекрывающихся фрагментов; соприкасающиеся фрагменты одинаковой высоты нужно объединять.

Пример ввода

5
20 30 10
1 10 40
30 10 20
80 10 20
60 20 30

Пример вывода

1 10 20
20 30 30
30 10 50
50 0 60
60 20 90
90 10 100
loading