KOI 전국 2016 초4- 장애물 경기 > 문제은행 : 정보올림피아드&알고리즘



2994 : 장애물 경기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
27 회   
시도횟수
176 회   

문제

 

평면 상에서 어떤 점의 위치를 나타내기 위해 좌표를 이용하면 매우 편리하다. 

<그림 1>에서 예로보인 것처럼 기준점(이를 원점이라 부른다)에서 

우측으로 거리가 4, 위로 거리가 3에 놓인 빨간점의 좌표는 (4, 3)로 표시한다.

좌표를 이용하면 평면 상에 있는 어떤 점의 위치도 쉽게 나타낼 수 있다. 

즉, 기준점에서 오른쪽으로 거리가 x, 위로 거리가 y에 놓인 점의 좌표는 (x, y)로 나타낸다.

기준점(원점)의 좌표는 (0, 0)이 된다.

 

 

 

장애물이 설치된 넓은 들판에서 재미있는 달리기 시합이 벌어진다. 

들판 곳곳에 수직방향(남북방향)으로 된 담장 모양의 장애물이 설치되어 있다. 

선수는 출발지점에서 동쪽방향으로 달리기 시작하다가 장애물을 만나면 남쪽 또는 북쪽으로 달려 장애물을 피해가야 한다. 

장애물 끝에 다다르면 다시 선수는 동쪽으로만 달릴 수 있다.

 

이 달리기의 목표는 결승선으로 지정된 (무한히 긴) 수직선에 가장 짧은 거리를 달려 도달하는 것이다. 

달리기 시작 전에 모든 장애물에 대한 정보가 선수에게 주어진다. 

즉, 어떤 크기의 장애물이 어느 위치에 놓여있는지에 대한 정보가 선수에게 주어지고, 

선수는 장애물을 피해가면서 가장 짧은 거리를 달려 결승선에 도착해야 한다.

 

선수의 출발지점 및 각 장애물 양 끝점의 위치는 (x, y)좌표를 사용하여 표시한다. 

모든 좌표 값은 정수로 주어지고, 출발지점의 x 좌표는 0이다. 

각 장애물은 수직선분으로 볼 수 있고, 이 때 양 끝 점의 x 좌표는 동일하기 때문에 

장애물에 대한 정보는 세 값 [x, y1, yh] (y1 < yh) 으로 나타낼 수 있다. 

이 세 값은 장애물이 설치된 곳의 x 좌표와 양 끝점의 y 좌표를 나타낸다.

 

x 좌표가 동일한 두 장애물이 겹치거나 또는 한 점에서 만나는 경우는 없다.

 

선수가 동쪽으로 달리다가 장애물의 끝 점을 만나면 계속 동쪽으로 달려간다.

 

<그림 2>의 예를 보자. 출발지점이 (0, 43), 결승선의 x 좌표가 70이고, 

4개의 수직 장애물에 대한 정보가 각각 [20, 30, 50], [30, 10, 38], [45, 35, 55], [55, 50, 70]인 경우, 

최단의 이동경로는 점선으로 표시한 것처럼 

(0, 43)→(20, 43)(20, 50)(45, 50)(45, 55)(55, 55)(55, 50)(70, 50)이 되고,

이때의 총 이동거리는 87이다. 또한 도착지점의 y 좌표는 50이 된다. 

 


 

 

<그림 3>의 예에선 서로 다른 최단경로가 다음과 같이 4개가 있다.

 

① (0, 40)→(20, 40)→(20, 50)→(35, 50)→(35, 60)→(70, 60)

② (0, 40)→(20, 40)→(20, 50)→(35, 50)→(35, 40)→(70, 40)

③ (0, 40)→(20, 40)→(20, 30)→(50, 30)→(50, 40)→(70, 40)

④ (0, 40)→(20, 40)→(20, 30)→(50, 30)→(50, 20)→(70, 20)

 


 

 


<그림 3>에서 보인 경로 가운데 경로 ②와 경로 ③은 달리는 경로는 다르지만 도착지점은 동일하다.

 

 

출발지점의 y 좌표, 결승선의 x 좌표, N개의 장애물에 대한 정보가 주어질 때 이동 규칙을 따르는 최단경로를 모두 찾은 후, 

도착지점이 서로 다른 최단경로의 도착지점의 y 좌표 값을 오름차순으로 차례로 출력하는 프로그램을 작성하시오.

 


입력형식

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 장애물의 개수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다.

다음 줄에는 출발지점의 y 좌표와 결승선의 x 좌표를 나타내는 두 정수가 차례로 주어진다. 

  이어지는 N 개의 줄 각각엔 장애물의 정보를 나타내는 세 정수 [x, yl, yh] (yl < yh)가 차례로 주어진다. 

  문제에서 사용되는 모든 좌표 (x, y)에 대해, 0 ≤ x ≤ 1,000,000 이고 0 ≤ y ≤ 2,000,000 이다. 

모든 장애물의 x 좌표는 0보다 크고 결승선의 x 좌표보다 작다.


출력형식

표준 출력으로 첫 번째 줄에는 최단경로의 길이를 출력한다.

두 번째 줄엔 최단경로들의 서로 다른 도착지점의 개수 k 와, k 개의 도착지점의 y 좌표를 오름차순으로 차례로 출력한다. 


부분문제의 제약 조건 

• 부분문제 1: 전체 점수 100점 중 13점에 해당하며 1 ≤ N ≤ 10 이고, 모든 좌표값 x, y 에 대해 0 ≤ x, y ≤ 500 이다. 

• 부분문제 2: 전체 점수 100점 중 22점에 해당하며 1 ≤ N ≤ 1,000 이고 모든 좌표값 x, y에 대해 0 ≤ x, y ≤ 500 이다. 

• 부분문제 3: 전체 점수 100점 중 29점에 해당하며 1 ≤ N ≤ 1,000 이다. 

• 부분문제 4: 전체 점수 100점 중 36점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.


입력 예

4 
43 70
30 10 38
20 30 50
45 35 55
55 50 70

출력 예

87
1 50

입력 예

3 
40 70
20 30 50
35 40 60
50 20 40

출력 예

90
3 20 40 60


경기도 안양시 동안구 평촌대로 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