#P6897. [ICPC 2014 WF] Messenger

[ICPC 2014 WF] Messenger

Description

平面上有两个移动的点 A,B,其中 A 想要向 B 发送一条信息。两个点会同时出发,各自沿着一个折线移动到终点为止。A 会在移动的途中发送一条信息,这条信息可以视作一个点 C,它会沿一条射线匀速运动,当 C 与 B 重合时,B 即可收到该信息。

A,B,C 的移动速度都是 1 单位长度每秒,A 最晚在它到达终点时发出信息,B 最晚需要在它到达终点时收到信息。令 tAt_A 代表发送信息的时间,tBt_B 代表接收信息的时间,那么你需要最小化 tBtAt_B-t_A 的值。特别地,如果 B 无论如何都无法收到信息,你需要输出 impossible

Input Format

第一行包含一个整数 nn,代表 A 经过折线的点数;
下面 nn 行,每行输入两个整数 xi,yix_i,y_i,依次描述 A 所走折线的点。
下面一行包含一个整数 mm,B 过折线的点数;
下面 mm 行,每行输入两个整数 ui,viu_i,v_i,描述 B 所走折线。

Output Format

一行,输出一个实数,代表答案。若无法满足,则输出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