На ось 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

   Решение

Тема:    [ Линейные рекуррентные соотношения ]

Сложность: 3 Классы: 9,10,11

Прислать комментарий

Условие

Пусть характеристическое уравнение (11.3) последовательности {a_n} имеет корень x₀ кратности 2. Докажите, что при фиксированных a₀, a₁ существует ровно одна пара чисел c₁, c₂ такая, что

Источники и прецеденты использования