배달원

시간 제한4초메모리 제한128 MB

요약

속력 1로 꺾은선 경로를 걷는 두 사람 사이에서 첫 번째 경로의 한 점에서 두 번째 경로의 한 점까지 속력 1인 심부름꾼이 직선으로 물건을 옮길 때 가장 짧은 전달 시간을 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Misha와 Nadia는 각각 2차원 평면 위의 경로를 따라 속도 1로 이동한다. Misha가 경로 위 어떤 지점에서 배달원에게 소포를 넘기면, 배달원은 직선으로 Nadia의 경로 위 한 지점까지 달려가 전달한다. 배달원도 속도 1이다. 소포를 넘긴 순간부터 Nadia가 받을 때까지 걸린 최소 시간을 구하라.

입력

Misha의 경로와 Nadia의 경로가 각각 주어진다. 각 경로는 방문 지점 수 $n$ 과 좌표 $(x_i,y_i)$ 목록이다. 두 사람은 동시에 출발하고 중간에 멈추지 않는다. 소포는 Misha가 마지막 지점에 도착하기 전까지, Nadia가 마지막 지점에 도착하기 전까지 전달되어야 한다.

출력

최소 배달 시간을 출력한다. 절대 오차 $10^{-3}$ 또는 상대 오차 $10^{-5}$ 이내로 출력한다. 불가능하면 impossible을 출력한다.

예제1

예제 1
입력
```
2
0 0
0 10
2
4 10
4 0
```
예상 출력
```
4.00000
```