문제
당신은 억울하게 누명을 써 감옥에 갇혔다. 당신은 다음과 같은 그림의 감옥에서 최단 경로를 찾아야 한다.
방은 항상 10.0크기의 정사각형이며, 다음 네 직선에 의해 결정되는 정사각형이다.
감옥은 항상 x = 0, x = 10, y = 0, 그리고 y = 10의 경계선을 갖는다.
당신은 처음에 (0,5)에 위치해 있고, 탈출을 위해서는 반드시 (10, 5)에 다다라야 한다.
감옥에는 최소 0에서 최대 18개의 벽이 y축과 평행하게 놓여 있다.
그림은 벽과 최단 경로를 나타낸다.
입력
입력은 벽의 수 n으로 시작한다. 다음 n줄에 걸쳐 각 벽에 대한 정보가 입력된다. 각 줄에는 먼저 벽의 x좌표값 x(0＜x＜10), 그리고 네 개의 y좌표값이 실수로 입력된다. 벽은 x좌표가 증가하는 순서로 입력되며, 각 벽에 대해서 y좌표값도 증가하는 순서로 입력된다.
출력
출력은 입력의 최단 경로의 거리를 출력하며, 소수 둘째 자리까지 출력한다.
예제
2
4 2 7 8 9
7 3 4.5 6 7
10.06
출처
1996 Mid-Central Regional Programming Contest B번
로그인해야 코드를 작성할 수 있어요.