아이언맨

JBLM MWR의 사진에서 잘라냄

아이언맨 철인삼종경기는 참가자들이 $3.86$ km를 수영하고, $180.25$ km를 자전거로 달린 뒤, 마지막으로 마라톤을 달리는 경기로, 가장 힘든 스포츠 경기 중 하나로 여겨진다. Viveka는 그보다도 더 어려운 대회인 $n$-애슬론을 위해 훈련해 왔다. $n$-애슬론 경기에서 참가자들은 출발점에서 도착점까지 물, 모래, 얼음, 아스팔트 등 여러 종류의 지형을 통과해야 한다. 경기를 더 흥미롭게 만들기 위해 참가자들은 자신의 능력에 가장 잘 맞는다고 생각하는 경로를 자유롭게 선택할 수 있다. 작년에 Viveka는 마지막 $40$ km를 얼음 위에서 $1$시간 만에 스케이트로 주파하여 장대한 승리를 거두었지만, 숙적 Veronica는 도착점에서 $1$ m 떨어진 타르 구덩이에 갇혔다.

올해의 지형 분포가 공개되었으며, 이제 Viveka 팀의 최적화 전문가인 당신은 그녀가 경기에서 가장 좋은 경로를 찾도록 도와야 한다. 대회는 평평한 지역에서 열리며, 이를 2D 평면으로 모델링한다. 각 지형 유형은 수평 띠 모양이다. 참가자들은 경기 구역을 벗어날 수 없다. 각 띠의 위치와 해당 지형에서 Viveka의 속력이 주어진다.

첫째 줄에는 십진수 두 쌍 $x_s$, $y_s$, $x_f$, $y_f$가 주어진다. 이는 각각 미터 단위로 나타낸 출발점과 도착점의 $x$좌표와 $y$좌표이다. 둘째 줄에는 층의 수를 나타내는 정수 하나 $n$ ($1 \leq n \leq 10\,000$)이 주어진다. 셋째 줄에는 층이 바뀌는 각 경계의 $y$좌표인 십진수 $n-1$개가 주어진다. 층은 순서대로 주어진다. 즉, $y_s < y_1 < y_2 < \cdots < y_{n-1} < y_f$이며, 따라서 $i$번 층의 모양은 $(-10\,000,10\,000)\times(y_{i-1},y_{i})$이다. 첫 번째 층과 마지막 층은 출발점과 도착점의 $y$좌표까지만 뻗어 있다. 즉, 각각의 모양은 $(-10\,000,10\,000)\times(y_s,y_1)$과 $(-10\,000,10\,000)\times(y_{n-1},y_f)$이다. 넷째 줄에는 각 층에서 Viveka의 초당 미터 단위 속력을 나타내는 십진수 $n$개가 주어진다. 모든 십진수의 절댓값은 최대 $10^4$이며 소수점 이하 자릿수는 최대 $4$개이다.

Viveka가 출발점에서 도착점까지 이동하는 데 필요한 최소 시간을 출력한다. 답의 절대 오차 또는 상대 오차는 최대 $10^{-6}$여야 한다.