COCI 2015/2016 contest2 3- 책상 옮기기(ARTUR) > 문제은행 : 정보올림피아드&알고리즘




2957 : 책상 옮기기(ARTUR)

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
1 회   
시도횟수
52 회   

문제

알고리즘 캠프가 끝나면 빌린 강의실을 정리해야 한다.

 

강의실을 정리하기 위해서는 우선 강의실에 배치한 책상들을 전부 옮겨야 한다. 

하지만, 무작정 옮겼다가는 책상 위에 있는 많은 짐들이 거슬린다. 따라서 사람들은 책상을 옮길 때 차근차근 조심해서 옮겨야 한다.

 

또, 이동 거리가 길수록 짐들이 사라질 가 능성이 많으므로, 아래 그림과 같이 y축 방향으로 아래쪽으로 움직인다. 

이 때 책상이 돌아가는 경우는 없다.

 

 


책상을 옮길 때, 책상을 옮기는 경로 상에 다른 책상이 있으면 안 된다. 

이때 책상의 양 끝이 닿는 것 도 안 된다. 

책상을 x축 아래로 옮겼으면, 짐을 모두 옮기고 책상은 기자재 본부로 반납한다.

 

당신은 N개의 책상을 문제 없이 옮길 수 있게 책상을 옮기는 순서를 정해야 한다. 

N개의 책상의 정 보가 주어졌을 때 책상을 옮기는 순서를 구하는 프로그램을 작성하여라. 

 


입력형식

첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 5,000) 두 번째 줄부터 N개의 줄에는 1번 책상부터 N번 책상에 대해서 각 책상의 양 끝 점의 x, y좌표가 주 어진다. 모든 좌푯값은 0 이상 10,000 이하이다.

출력형식

첫 번째 줄에 옮겨야 할 책상의 번호를 먼저 옮기는 순서대로 출력한다. 답이 여러 개이면 그중 가장 먼저 옮기는 책상의 번호가 가장 작은 것을 출력한다. 그래도 답이 여러 개이면 그 중 2번째로 옮기는 책 상의 번호가 가장 작은 것을 출력한다. 이런 식으로 반복하여 가장 앞선 답을 출력한다.

입력 예

4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3

출력 예

2 1 4 3

입력 예

4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1

출력 예

1 2 4 3

입력 예

3
4 6 5 5
2 1 15 1
3 2 8 7

출력 예

2 3 1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP