UVA1702 Messenger

米沙 (Misha) 需要寄送包裹给他的朋友娜迪亚 (Nadia)。他们两人经常在广袤的俄罗斯各地旅行。因此他们决定雇佣一个信使。由于信使服务的费用取决于递送包裹所需的时间，他们需要你的帮助来稍作优化。 假设米沙和娜迪亚在一个二维平面上移动，各自访问一系列地点，并在地点之间沿着直线段移动。你的任务是根据他们各自的路径，找出最短的可能递送时间。 米沙在他路径上的某个点将包裹交给信使。信使从取件点出发，毫不延迟地沿着直线移动，去拦截正在自己路径上移动的娜迪亚。米沙、娜迪亚和信使都以每单位时间 $1$ 单位距离的恒定速度移动。 递送时间是指从米沙交出包裹到娜迪亚收到包裹之间的时间。

输入文件包含若干组测试用例，每组的格式如下所述。 每组测试用例包含两条路径描述，第一条是米沙的，第二条是娜迪亚的。每条路径描述以包含一个整数 $n$ 的行开始，表示访问的地点的数量 ($2 \le n \le 50000$)。接下来是 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，指定一个地点的坐标 ($0 \le x_i, y_i \le 30000$)。地点的坐标按照访问的顺序列出，并且相邻的地点坐标不同。 米沙和娜迪亚同时开始他们的旅程，沿着各自的路径访问地点，中途不停留。每条路径的总长度最多为 $10^6$。包裹最迟必须在米沙到达他的终点时被取走，并且最迟必须在娜迪亚到达她的终点时被送达。

对于每组测试用例，输出必须遵循以下描述，占一行。 输出递送所需的最短时间。答案的绝对误差最多为 $10^{-3}$ 或相对误差最多为 $10^{-5}$。如果包裹无法送达，则输出 `impossible`。