#P4107. [Wf2015]Asteroids
[Wf2015]Asteroids
[ICPC2015 WF] Asteroids
题目描述
两颗小行星干扰了通信中继站。Han 想在两颗小行星重合得最多时,用一枚导弹同时摧毁它们。他屏幕上的每颗小行星都是一个二维凸多边形,以给定速度平移,形状和朝向始终不变。
求在 的某个时刻,两颗小行星的重叠面积可以达到最大时,最早的那个时刻。

上图对应样例 1,虚线标出小行星随后每隔 秒出现的位置。两颗小行星在 秒后开始接触,最大重叠发生在第 秒与第 秒之间。
输入格式
输入两行,每行描述一颗小行星,依次给出整数 。
其中 ()为顶点数, 为时刻 的顶点坐标,按顺时针给出,且 。 为小行星在两个坐标轴上的速度分量,单位为坐标单位每秒,且 。每条边的长度不超过 。两颗小行星在 时既不重叠,也不接触。
输出格式
若两颗小行星曾有正面积重叠,输出使重叠面积最大时的最早时刻。若它们只接触而从无正面积重叠,输出最早接触时刻。若它们从不接触也不重叠,输出 never。
时刻以秒为单位,答案的绝对误差或相对误差不超过 即可。
样例 #1
样例输入 #1
6 3 2 2 4 3 6 6 6 7 4 6 2 2 2
4 18 5 22 9 26 5 22 1 -2 1
样例输出 #1
4.193518
样例 #2
样例输入 #2
4 0 0 0 2 2 2 2 0 -1 1
4 10 0 10 2 12 2 12 0 1 1
样例输出 #2
never