Informatica Online Judge

  SKY LINE I [0540 / 021C]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 118   Total Tried : 1027


The Champion of this Problem (C++) : gs17003 - 0ms / 385byte
My Best Submission (C++) : N/A

[]

Background

스카이 라인이란 수평선을 바라볼 때 건물들의 배치에 따라 나타난 건물의 외곽선을 연결한 것을 말한다.

아래 그림은 어느 도시의 스카이라인을 보여준다.

아래 도시는 4개의 건물이 있으며 건물 1은 x좌표상으로 1~20까지의 폭과 5의 높이를 가진다.

이와 같은 식으로 4개의 건물이 존재한다.

각 건물의 정보가 입력으로 주어질 때, 스카이라인의 정보를 출력하는 프로그램을 작성하시오.



단 스카이라인을 출력할 때는 위 그림의 빨간 점의 정보만 출력하도록 하자.

Input

첫 번째 줄에 건물의 수 n이 입력된다. (단, n은 5000이하의 자연수)
다음 줄 부터 n줄에 걸쳐서 건물의 왼쪽 x좌표, 높이의 y좌표, 오른쪽 x좌표가 공백으로 구분되어 입력된다. (각 좌표 및 높이값은 10,000이하의 자연수)

Output

출력은 스카이라인의 꺽이는 점의 x좌표와 높이 공백으로 구분하여 한 줄에 하나씩 출력한다.
(꺽이는 점이란 상승 중인 스카이라인은 상승이 끝나는 높이, 하강 중인 스카이라인은 하강이 끝나는 높이를 출력한다.)

IO Example

입력
4
1 5 20
3 7 5
6 2 7
21 2 23

출력
1 5
3 7
5 5
20 0
21 2
23 0

출제 및 Data제작 : Seaguy

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]