K미술관은 많은 벽으로 구성된 특이한 구조를 가진 건축물로 유명하다.

미술관의 내부 조명을 위해서 두 개의 전등이 한 쪽 벽의 양 끝 모서리에 설치되어 있는데, 건물의 내부에 조명이 미치지 않는 곳이 없다.

즉, 건물 내부의 모든 장소는 적어도 하나의 전등으로부터 조명을 받을 수 있다.

정보올림피아드를 준비하는 홍길동은 이 미술관 건물을 좋아해서 시간이 날 때마다 관람하러 온다.

하루는 미술관을 관람하던 중에 갑자기 “미술관 내부의 두 지점을 연결하는 최단 경로는 어떤 모양일까?”라는 의문점이 떠올랐다.

일반적인 다각형에서 최단 경로 알고리즘을 구현하는데 힘들었던 기억을 되살리면서, 두 개의 전등으로 모든 곳을 비출 수 있는 미술관의 특이한 구조 때문에 최단 경로를 쉽게 구할 수 있지 않을까라는 생각을 하게 되었다.

미술관을 n개의 정점을 가진 다각형 P=(v_0, v_1, ..., v_{n-1})로 나타낼 수 있다.

정점 리스트는 다각형의 경계선을 반시계방향으로 따라가면서 정점들을 순서대로 나열한 것이다.

미술관에서 전등이 설치된 장소를 정점 v_0과 v_1이라고 하자. 에지 (v_0, v_1)은 수평 선분으로 v_0의 x-좌표는 항상 v_1의 x-좌표보다 작다.

v_0과 v_1을 제외한 나머지 모든 정점의 y-좌표는 v_0의 y-좌표보다 크다(그림 1 참조).

미술관 내부의 어떤 장소 q가 전등 v의 조명을 받는다는 것은, 두 점 q와 v를 연결하는 선분이 P의 외부와 만나지 않는다는 것을 말한다.

P의 모든 점은 v_0또는 v_1로부터 조명을 받는다는 사실에 유의하라.

그림 1의 다각형에서 정점 v_8과 v_{11}은 v_1로부터만 조명을 받고, v_3과 v_4는 v_0으로부터만 조명을 받는다.

나머지 정점들은 v_0과 v_1 둘 다로부터 조명을 받는다.

두 정점 사이의 최단 경로가 항상 다각형의 정점에서만 꺾인다는 것은 잘 알려져 있다.

예를 들어, 두 정점 v_4와 v_{11}사이의 최단 경로는 (v_4, v_5, v_9, v_{11})이다. 두 정점 v_5와 v_1 사이의 최단 경로는 하나의 선분인 (v_5 ,v_1)이다.

홍길동을 도와서 다각형 P의 두 정점이 주어질 때, 두 정점 사이의 최단 경로를 구하는 프로그램을 작성하시오.

미술관 timer 1초 memory 128MB

미술관 1초 128MB