НачалоПодразделы
Другие разделы
Дата и время
08/05/2024 13:00:28
Занятие 14
B. Линия горизонта
Сканирование, метод двух указателейОлимпиадные задачи на русском языке
| 20/02/2008 | Занятие 14 (B) |
| 11/04/2009 | Занятие 17 (D) |
| 19/02/2014 | Занятие 14 (B) |
| 24/10/2021 | «Базовая олимпиадная подготовка» (second level) - Сканлайн (проводит novink) (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вдоль прямой улицы стоят дома – прямоугольные параллелепипеды. Нужно найти линию горизонта – ломанную,
"отделяющую дома от неба" при взгляде сбоку.
Первая строка ввода содеджит одно целое число `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
