P6905 [ICPC 2015 WF] Asteroids

今年是 $2115$ 年。小行星通信中继系统是十年前由小行星通信部建立的。有一个小问题——小行星太多，它们很危险！比较小的小行星不仅不断干扰中继站的信号，而且对在中继站之间飞行的所有维修飞机也是一种危险。这些小行星必须被摧毁！防止危险的星际联盟（ICPC）已被下达移除这些危险的小行星的指令，并请了一支精英团队来完成这项工作。Han Duo 是这个小行星驱逐舰小组的队长。Han Duo 带着他的导弹飞过小行星带，炸毁了 ICPC 认为的令人讨厌的任何小行星。

ICPC 没那么多钱。后果是 Han Duo 和他的团队没有他们想要的那么多导弹，因此他们无法炸毁所有麻烦的小行星。但是小行星很小，导弹也很强大。因此，如果两颗小行星彼此靠近并正确排列，就有可能用一枚导弹将两者都摧毁。 Han Duo 的屏幕将小行星显示为非旋转的二维简单凸多边形，每个多边形都以固定速度移动。他认为撞击两颗小行星的最佳时间是两个多边形的重叠达到最大值时。例如，图 $1$ 演示了样例输入 $1$，显示了两颗小行星及其后续的位置，间隔 $1$ 秒。两颗小行星在 $33$ 秒后开始接触，最大重叠区域出现在 $44$ 到 $55$ 秒之间。 图 $1$：样例输入 $1$。两颗有交叉路径的小行星。 计算两颗小行星的最大重叠时间需要计算机来完成，但不幸的是，Han Duo 在飞行学院的大部分程序设计课中都在睡大觉。现在把这个任务交由你。

输入包括两个小行星规格。每个形式为 $n, x_1, y_1 ,x_2,y_2 \cdots x_n ,y_n ,v_x, v_y$，其中 $n$（$3 \le n \le10$）是顶点的数量，每个 $x_i,y_i$（$-10000 \leq x_i,y_i \leq 10000$）在屏幕上按顺时针顺序给出的小行星顶点的坐标，$v_x,v_y$（$-100 \le v_x,v_y \le 100$）是小行星的 $x$ 和 $y$ 速度（单位/秒），$x,y$ 值代表 $t=0$ 时每个小行星的位置，此时多边形不相交或接触。小行星任意一侧的最大长度为 $500$。输入中的所有数字都是整数。

以秒为单位输出两个多边形具有最大相交的时间，如果存在多个多边形，则使用最早的时间。如果两个多边形从不重叠，而是彼此接触，则将其视为公共面积为零的交点，并输出最早的时间。如果多边形从不重叠或接触，则输出 `never`。你应该只考虑确定的时候。输出的绝对或相对的误差应不超过 $10^{-3}$。

时间限制：$2000$ 毫秒，内存限制：$1048576$ kB。 2015年国际大学生编程大赛（ACM-ICPC）世界总决赛。