#P4107. [Wf2015]Asteroids

    ID: 3315 传统题 2000ms 128MiB 尝试: 32 已通过: 7 难度: 9 上传者: 标签>难度分类提高+/省选-模拟与实现技巧坐标变换计算几何分离轴定理投影离线与分治事件排序多项式与生成函数分段多项式半平面交叉积鞋带公式CF2600

[Wf2015]Asteroids

[ICPC2015 WF] Asteroids

题目描述

两颗小行星干扰了通信中继站。Han 想在两颗小行星重合得最多时,用一枚导弹同时摧毁它们。他屏幕上的每颗小行星都是一个二维凸多边形,以给定速度平移,形状和朝向始终不变。

求在 t>0t>0 的某个时刻,两颗小行星的重叠面积可以达到最大时,最早的那个时刻。

样例 1 中两颗小行星及它们每隔一秒的位置

上图对应样例 1,虚线标出小行星随后每隔 11 秒出现的位置。两颗小行星在 33 秒后开始接触,最大重叠发生在第 44 秒与第 55 秒之间。

输入格式

输入两行,每行描述一颗小行星,依次给出整数 n,x1,y1,…,xn,yn,vx,vyn,x_1,y_1,\ldots,x_n,y_n,v_x,v_y。

其中 nn(3≤n≤103\le n\le10)为顶点数,(xi,yi)(x_i,y_i) 为时刻 t=0t=0 的顶点坐标,按顺时针给出,且 −10 000≤xi,yi≤10 000-10\,000\le x_i,y_i\le10\,000。(vx,vy)(v_x,v_y) 为小行星在两个坐标轴上的速度分量,单位为坐标单位每秒,且 −100≤vx,vy≤100-100\le v_x,v_y\le100。每条边的长度不超过 500500。两颗小行星在 t=0t=0 时既不重叠,也不接触。

输出格式

若两颗小行星曾有正面积重叠,输出使重叠面积最大时的最早时刻。若它们只接触而从无正面积重叠,输出最早接触时刻。若它们从不接触也不重叠,输出 never。

时刻以秒为单位,答案的绝对误差或相对误差不超过 10−310^{-3} 即可。

样例 #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