공항 물류

공항에는 홀과 터미널을 잇는 통로에 무빙워크가 깔려 있는 곳이 많다. 승객은 바닥을 걷는 대신 무빙워크에 올라서 있어도 되고, 무빙워크 위를 걸으면 통로 끝까지 훨씬 빨리 갈 수 있다.

델프트 시립 공항도 같은 방식을 쓴다. 다만 최신 공항 설계 유행을 따라 통로가 따로 없다. 공항 전체가 하나의 큰 홀이고, 컨베이어 여러 개가 바닥 위에 아무 위치와 아무 방향으로 놓여 있다.

지점 $A$에서 지점 $B$까지 갈 때는 바닥을 걷는 것과 컨베이어 위를 걷는 것을 마음대로 섞어도 된다. 컨베이어의 어느 지점에서든 올라타고 내릴 수 있고, 컨베이어에 올라서지 않고 그대로 가로질러 갈 수도 있다.

바닥을 걷는 속력은 초당 1미터다. 컨베이어의 진행 방향으로 걸으면 전체 속력이 초당 2미터가 된다.

컨베이어의 진행 방향을 거슬러 걷는 것은 아무 이득이 없고 금지되어 있다. 대신 컨베이어 바로 옆 바닥은 걸어도 된다. 컨베이어의 두께는 없다고 본다.

$A$에서 $B$까지 가는 데 걸리는 최소 시간을 구하라.

그림 1: 첫 번째 예제 입력의 최단 경로.

첫째 줄에 실수 네 개 $X_A$, $Y_A$, $X_B$, $Y_B$가 주어진다. 출발 지점은 $A = (X_A, Y_A)$, 도착 지점은 $B = (X_B, Y_B)$다.

둘째 줄에 홀에 놓인 컨베이어의 개수 $N$이 주어진다 ($0 \le N \le 100$). 이어지는 $N$개 줄에는 각각 실수 네 개 $X_1$, $Y_1$, $X_2$, $Y_2$가 주어진다. 이 컨베이어는 $(X_1, Y_1)$에서 시작해 $(X_2, Y_2)$에서 끝나고, 시작점에서 끝점까지 직선으로 이어진다.

모든 좌표는 미터 단위의 실수이고 $0 \le X, Y \le 1000.0$이다.

컨베이어의 길이는 1미터 이상이다. 서로 다른 두 컨베이어는 교차하지도 닿지도 않는다. 출발 지점과 도착 지점은 어떤 컨베이어 위에도 놓이지 않는다.

$A$에서 $B$까지 가는 데 걸리는 최소 시간을 초 단위로 한 줄에 출력한다. 소수점 아래 여섯째 자리까지 반올림해 출력한다.

채점은 출력 문자열을 그대로 비교한다. 여섯째 자리가 맞게 나오도록 충분히 정확하게 계산해야 한다.