익스트림 슬라롬

자동차 회사 Moving이 스위치백 구간을 달리는 새 탈것을 개발했다. 이 기계는 어느 방향으로든 같은 속력으로 움직이고 방향을 바꾼다.

회사는 이 탈것을 홍보하려고 익스트림 슬라롬이라는 대회를 열었다. 익스트림 슬라롬 코스는 1번부터 차례로 번호가 붙은 게이트로 이루어지고, 게이트는 각각 하나의 선분이다. 주자는 1번 게이트에서 출발해 번호 순서대로 게이트를 지나거나 스치면서 마지막 게이트까지 달린다. 목표가 아닌 게이트를 지나거나 스쳐도 되지만, 통과로 세지 않는다.

당신의 팀도 다음 대회에 나간다. 우승하려면 가장 짧은 경로로 달려야 한다. 동료를 돕도록 최단 길이를 구하는 프로그램을 작성한다.

익스트림 슬라롬 코스의 예

입력은 여러 개의 코스로 이루어진다.

각 코스의 첫 줄에는 게이트의 개수 $n$ ($2 \le n \le 12$)이 주어진다. 이어지는 $n$개의 줄에는 통과할 순서대로 게이트가 하나씩 주어진다. 각 줄에는 게이트의 두 끝점을 나타내는 정수 $x_1$, $y_1$, $x_2$, $y_2$ ($0 \le x_1, y_1, x_2, y_2 \le 100$)가 주어진다. 어떤 두 게이트도 서로 닿거나 교차하지 않는다.

입력의 마지막 줄에는 0 하나만 주어진다.

코스마다 최단 길이를 한 줄에 하나씩 출력한다. 값은 소수점 아래 넷째 자리까지 반올림해 출력하고, 빈 자리는 0으로 채워 넷째 자리까지 모두 적는다. 정확한 답은 반올림 경계에서 $10^{-5}$ 이상 떨어져 있으므로 넷째 자리 값은 하나로 정해진다.