레이팅 미적용Misha는 친구 Nadia에게 소포를 보내야 한다. 두 사람 모두 아주 넓은 러시아 곳곳을 자주 여행한다. 그래서 그들은 배달부를 고용하기로 했다. 배달 서비스 비용은 소포를 배달하는 데 걸리는 시간에 따라 달라지므로, 조금이라도 최적화하려면 당신의 도움이 필요하다. Misha와 Nadia는 2차원(t\(wo-di\)mensional) 평면 위에서 움직이며, 각자 일련의 장소들을 방문하면서 장소에서 장소로 직선 선분을 따라 이동한다고 하자. 당신의 임무는 두 사람의 경로가 주어질 때 가능한 최단 배달 시간을 구하는 것이다. Misha는 자신의 경로 위 어떤 지점에서 배달부에게 소포를 건넨다. 배달부는 수령 지점(pi\(ck-up\))에서 지체 없이 직선으로 이동하여, 자신의 경로를 따라 이동 중인 Nadia를 가로챈다. Misha, Nadia, 배달부는 모두 시간 단위당 1 거리 단위의 일정한 속력으로 움직인다. 배달 시간은 Misha가 소포를 건넨 순간부터 Nadia가 받는 순간까지의 시간이다.
입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스에는 두 개의 경로 설명이 있는데, 첫 번째는 Misha의 것이고 두 번째는 Nadia의 것이다. 각 경로 설명은 방문하는 장소의 수인 정수 \(n\) (\(2 \le n \le 50\,000\))이 있는 줄로 시작한다. 이어서 \(n\)개의 줄에 각각 장소의 좌표를 지정하는 두 정수 \(xi\)와 \(yi\) (\(0 \le x_{i}\), \(y_{i} \le 30\,000\))가 주어진다. 장소들의 좌표는 방문할 순서대로 나열되며, 연속한 장소들이 같은 좌표를 갖지는 않는다. Misha와 Nadia는 같은 시각에 여정을 시작하여 멈추지 않고 각자의 경로를 따라 장소들을 방문한다. 각 경로의 길이는 최대 \(10^{6}\)이다. 소포는 늦어도 Misha가 마지막 장소에 도착할 때까지 수령되어야 하고, 늦어도 Nadia가 마지막 장소에 도착할 때까지 배달되어야 한다.
배달에 필요한 최소 시간을 출력한다. 답의 절대 오차는 \(10^{−}^{3}\) 이하이거나 상대 오차는 \(10^{−}^{5}\) 이하여야 한다. 소포를 배달할 수 없으면 대신 impossible을 출력한다.
2
0 0
0 10
2
4 10
4 0
4.00000
2
0 0
1 0
3
2 0
3 0
3 10
5.00000