Ни один день победы в Берляндии не обходился без парада военной техники. Этот год не является исключением. В связи с этим подготовка уже идёт полным ходом. Танки уже строятся в одну колонну, артиллерийские установки готовы стрелять, солдаты маршируют на главной площади... А у генерала военно-воздушных сил Генералова опять неприятности. За последний год в Берляндии полным ходом шло строительство небоскрёбов, поэтому самолётам теперь не так просто летать по городу. Было решено, что все самолёты будут лететь строго с юга на север, при этом на всём пути самолёта не должно встретиться ни одного небоскрёба, иначе праздник закончится трагически. В министерстве строительства были получены данные об n небоскрёбах (остальные здания достаточно маленькие и самолётам не помешают). Если смотреть на город с юга на север как на плоскость, то i-ое здание представляет собой прямоугольник высоты hi. Его самая западная точка имеет абсциссу li, а самая восточная точка — ri. Рельеф местности в городе плоский, поэтому основания всех зданий находятся на одном уровне. Ваша задача, как главного программиста министерства обороны, по данным о небоскрёбах найти огибающую ломаную, то есть такую что:
В первой строке входного файла задано целое число n (1 ≤ n ≤ 100000). Следующие n строк содержат по три целых числа hi, li, ri (1 ≤ hi ≤ 109, - 109 ≤ li < ri ≤ 109).
В первой строке выведите целое число m — количество вершин огибающей ломаной. Следующие m строк должны содержать по 2 целых числа — позицию и высоту вершины ломаной. Вершины ломаной выдавайте в порядке обхода ломаной с запада на восток. Помните, что первая и последняя вершины ломаной должны располагаться на высоте 0.
2 3 0 2 4 1 3
6 0 0 0 3 1 3 1 4 3 4 3 0
5 3 -3 0 2 -1 1 4 2 4 2 3 7 3 6 8
14 -3 0 -3 3 0 3 0 2 1 2 1 0 2 0 2 4 4 4 4 2 6 2 6 3 8 3 8 0
2000 ms 64 Mb Правила оформления программ и список ошибок при автоматической проверке задач