시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB174938618919.033%

문제

원래 징검다리는 단순히 개울을 건너기 위해 만든 것이다. 그러나 놀이를 좋아하는 사람들은 이 징검다리 위를 달리는 경기를 하기로 하였다.

징검다리가 놓여 있는 위치는 (x, y) 순서쌍으로 표현된다. 시작점은 언제나 (0,0) 원점이다. 경기가 진행되는 동안 여러분들은 현재 위치한 징검다리와 x좌표 차이가 2 이하이고, y좌표 차이도 2 이하인 징검다리로만 점프할 수 있다. 결승선은 x축에 평행한 직선인데, 여러분이 결승선과 y좌표가 동일한 징검다리에 도달하면, 결승선을 통과한 것이므로 경기가 끝난다.

징검다리들의 위치가 주어지면, 경기에서 승리하기 위해, 가장 빠른 경로를 찾아내는 프로그램을 작성하시오. 가장 빠른 경로란, 경로를 구성하고 있는 점프들의 길이 합이 최소인 경로이다. (x1, y1)에 위치한 징검다리에서 (x2, y2)에 위치한 징검다리로의 점프는 루트((x1-x2)^2+(y1-y2)^2)의 길이를 갖는다고 정의한다.

입력

첫째 줄에 징검다리의 개수 N과, 결승선의 y좌표 F가 주어진다. 둘째 줄부터는 N개의 징검다리들의 좌표가 한 줄에 하나씩 주어진다. N은 50,000 이하의 자연수이다. F나 각 좌표들은 0 이상 100만 이하의 정수이다. y좌표가 F를 초과하는 징검다리는 입력되지 않는다. (0,0)은 N개의 징검다리 중 하나로 입력되지 않지만, 여러분의 시작점임을 명심한다.

출력

첫째 줄에, 가장 빠른 경로의 길이를 소수 첫째 자리에서 반올림하여, 정수로 출력하도록 한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

5 3
1 2
6 3
4 1
3 2
0 2

예제 출력 1

8

힌트

(0,0) - (1,2) - (3,2) - (4,1) - (6,3)의 경로를 따라 가면 8.4787...의 길이를 갖는 경로가 되며, 이것이 최단 경로이다.

출처