문제
대도시의 야경은 으례 높고 네모난 건물들로 뒤덮이기 마련이다. 서울 시내의 야경도 많은 건물들이 서로 잘 구분되지 않을 만큼 어둡게 보이며, 그 윤곽선들이 모여 스카이라인을 이루게 된다. 위 그림은 건물들의 배치를 나타내고 있다. 이 건물들이 밤에는 아래와 같이 아경을 만든다.
건물들의 위치와 높이가 주어질 때, 도시의 스카이라인을 출력하는 프로그램을 작성하시오
|
입력
첫 줄에 건물의 수가 주어진다. 그 다음 줄부터는 한 줄에 한 건물씩, 각 건물의 왼쪽 끝 좌표, 오른 쪽 끝 좌표, 높이가 사이에 한 칸의 공백을 두고 주어진다. 건물의 개수는 최대 100개이며, 건물의 좌표는 0~5000, 높이는 0~1000의 범위를 갖는 정수이다.
출력
첫 줄에는 구간의 수를 출력한다. (여기서 구간이란 연속해서 높이가 같은 부분을 의미한다.) 그 다음 줄부터는 한 줄에 한 구간씩 그 구간의 시작 좌표, 끝 좌표, 높이를 사이에 한 칸의 공백을 두고 출력한다. 구간은 좌표가 작은 것부터 차례대로 출력하는데, 구간끼리 교차하는 부분이 있어서는 안되며, 중간에 건물이 없는 경우에도 높이가 0인 구간으로 출력해야 한다. 그리고 인접한 구간의 높이가 같아서도 안된다.
예시 1
입력
10
10 75 40
20 35 90
25 90 20
45 100 140
80 140 70
110 130 80
160 195 40
165 200 50
175 205 100
215 225 70
출력
13
10 20 40
20 35 90
35 45 40
45 100 140
100 110 70
110 130 80
130 140 70
140 160 0
160 165 40
165 175 50
175 205 100
205 215 0
215 225 70