QOJ.ac

QOJ

حد الوقت: 2 s حد الذاكرة: 1024 MB مجموع النقاط: 100

#4677. 小行星

الإحصائيات

2115 年,小行星通信中继系统由小行星通信部建立已有十年。除了一个小问题外,它运行良好——小行星太多了!较小的小行星不仅干扰中继站的信号,还对往返于各站之间的维护飞行器构成威胁。这些小行星必须被摧毁!行星际灾难预防联盟(ICPC)负责清除这些危险的小行星,并聘请了一支精英飞行员团队来执行这项任务。Han Duo 是这支小行星摧毁者团队的队长。他装备着导弹,驾驶飞船穿梭于小行星带,炸毁任何 ICPC 认为碍事的小行星。

ICPC 目前面临一些不幸的预算问题。结果之一是 Han 和他的团队没有他们想要的那么多导弹,因此他们无法炸毁所有麻烦的小行星。但小行星很小,导弹威力很大。因此,如果两颗小行星彼此靠近并排列得当,就有可能用一枚导弹同时摧毁两颗。

Han 的屏幕将小行星显示为不旋转的二维简单凸多边形,每个多边形以固定的速度移动。他决定,击中两颗小行星的最佳时机是两个多边形重叠面积最大时。例如,图 B.1 展示了样例输入 1,显示了两颗小行星及其在 1 秒间隔后的位置快照。这两颗小行星在 3 秒后开始接触,最大重叠面积出现在 4 到 5 秒之间。

图 B.1:样例输入 1。两条路径交叉的两颗小行星。

计算两颗小行星何时出现最大重叠需要一些编程知识,但不幸的是,Han 在飞行学院的大部分编程课上都在睡觉。这就是你需要介入的地方。

输入格式

输入包含两颗小行星的规格说明。每颗小行星的格式为 $n \ x_1 \ y_1 \ x_2 \ y_2 \ \dots \ x_n \ y_n \ v_x \ v_y$,其中 $n$ ($3 \le n \le 10$) 是顶点数,每个 $x_i, y_i$ ($-10\,000 \le x_i, y_i \le 10\,000$) 是 Han 屏幕上小行星顶点的坐标,按顺时针顺序给出,$v_x, v_y$ ($-100 \le v_x, v_y \le 100$) 是小行星在 $x$ 和 $y$ 方向上的速度(单位:单位/秒)。$x_i, y_i$ 的值指定了小行星在时间 $t=0$ 时的位置,此时多边形不相交也不接触。小行星任意一边的最大长度为 500。输入中的所有数字均为整数。

输出格式

显示两个多边形具有最大交集的时间(以秒为单位),如果存在多个这样的时间,则使用最早的时间。如果两个多边形从不重叠但会接触,则将其视为公共面积为零的交集,并显示最早的此类时间。如果多边形从不重叠也不接触,则显示 never。你只需要考虑正时间。你的输出应具有不超过 $10^{-3}$ 的绝对或相对误差。

样例

样例输入 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

4 0 0 0 2 2 2 2 0 -1 1
4 10 0 10 2 12 2 12 0 1 1

样例输出 2

never

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.