과학자 레가타

1996년부터 매년 전 세계의 컴퓨터 과학자들이 모여 유명한 과학자 레가타를 연다. 이 대회는 바다 위의 장애물을 피해 가는 보트 경주다. 모든 팀은 같은 출발점에서 출발하며, 어떤 장애물에도 닿거나 가로지르지 않고 도착점에 이르러야 한다. 장애물에 닿거나 장애물을 가로지른 팀은 즉시 실격된다. 도착점에 가장 먼저 도착한 팀이 우승하며, 도착점은 출발점과 다르다.

당신은 브라질 팀의 의뢰를 받아 출발점에서 도착점까지 가는 유효한 경로 중 가장 짧은 경로의 길이를 구하는 프로그램을 만들게 되었다.

바다는 무한한 평면이다. 각 장애물은 고정된 위치에 있으며, 두 끝점 $(x_1, y_1)$과 $(x_2, y_2)$로 주어지는 선분이다. 보트는 크기가 없는 평면 위의 점이고, 장애물의 두께는 무시한다.

장애물끼리는 서로 만나지 않는다. 마찬가지로 출발점과 도착점은 어떤 장애물 위에도 있지 않다.

보트는 장애물에 원하는 만큼 가깝게 붙어 지나갈 수 있다. 따라서 구해야 하는 값은 유효한 경로 길이의 하한이며, 이 값은 장애물의 끝점을 지나가거나 장애물을 따라 스치듯 움직이는 경로도 허용한다고 보고 계산한 최단 거리와 같다. 장애물의 내부를 가로지르는 경로는 여전히 허용되지 않는다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 다섯 개 $x_i$, $y_i$, $x_f$, $y_f$, $n$이 주어진다. 차례대로 출발점의 좌표 $(x_i, y_i)$, 도착점의 좌표 $(x_f, y_f)$, 장애물의 개수 $n$ $(0 \le n \le 150)$이다. 이어지는 $n$개의 줄에는 각각 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어지며, 한 장애물의 두 끝점의 좌표를 나타낸다. 모든 점의 좌표 $x$, $y$는 $-5000 \le x, y \le 5000$을 만족한다.

입력의 끝은 $x_i = y_i = x_f = y_f = n = 0$인 줄로 나타낸다.

각 테스트 케이스마다 가장 짧은 유효한 경로의 길이를 소수점 아래 둘째 자리까지 반올림하여 한 줄에 출력한다. 소수점 아래 숫자는 항상 정확히 두 자리를 출력한다.