QOJ.ac

QOJ

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

#5106. 天空之岛

الإحصائيات

你可能从未听说过 Iceepeecee 群岛,但这正合当地居民的心意。该群岛位于南太平洋的偏远地区,远离常规航线和海路,真正处于人迹罕至之处,并保留了未受破坏的当地动植物群,堪称热带天堂。

当你不希望被成群的游客打扰时,远离地图是一件好事,但当你出于某种原因确实需要地图时,情况就不那么理想了。最近就出现了这样一个原因:Iceepeecee 的中央政府需要一份精确的岛屿地图来分配政府资金。即使是热带天堂也需要钱,所以 Iceepeecee 需要一张地图!

制作地图最简单的方法是进行航空测量。在排除了包租飞机(太贵)、建造热气球(太危险)以及给信鸽装上摄像头(对动物太残忍)等方案后,他们想出了一个绝妙的主意。尽管地理位置偏远,但仍有许多商业飞机飞越 Iceepeecee 的上空。如果能在已经安排好的航班上安装摄像头呢?这将是一个廉价的解决方案!

Iceepeecee 的计划是在飞机上安装线扫描相机。这些相机垂直向下拍摄,每次收集一条与飞行路径正交的线段图像。拍摄的线段由飞机的飞行高度和相机的孔径角 $\theta$ 决定(见图 F.1)。孔径角 $\theta$ 越大,相机能看到的范围就越广,但相机的成本也越高。

此外,Iceepeecee 希望确保每个岛屿都能被至少一次飞行完整地观测到。这意味着,仅仅通过多次飞行将一个岛屿部分拍摄下来是不够的,即使这些照片组合起来覆盖了整个岛屿也不行。

飞行路径遵循三维空间中的直线段,即 $(x_1, y_1, z_1) - (x_2, y_2, z_2)$(见图 F.2),其中 $z$ 坐标表示飞机的高度。照片仅沿这些线段拍摄。

给定岛屿和飞行路径的位置,Iceepeecee 希望找到能成功完成测量的最小孔径角 $\theta$。你能帮忙吗?

图 F.1:飞机的正面视图。其相机指向下方,可以看到飞机下方绿色所示的地面部分。可见范围的大小取决于孔径角 $\theta$。

图 F.2:通过两条飞行路径测量三个岛屿。这对应于第一个样例输入。(a) 三个岛屿(黑色所示)和两条飞行路径(红色和绿色)。未显示高度。(b) 阴影区域表示在最优选择的 $\theta$ 下,两条飞行路径上可见的地面。

输入格式

输入描述了一组岛屿和飞行路径。第一行包含两个整数 $n$ 和 $m$,分别表示岛屿的数量和飞行路径的数量 ($1 \le n, m \le 100$)。接下来是 $n$ 个岛屿的描述。每个岛屿的描述以一行开始,包含一个整数 $n_i$,表示描述第 $i$ 个岛屿的多边形的顶点数 ($3 \le n_i \le 100$)。随后是 $n_i$ 行,每行包含两个整数 $x_{ij}, y_{ij}$ ($|x_{ij}|, |y_{ij}| \le 10^6$),按逆时针顺序指定第 $i$ 个岛屿的顶点。每个岛屿的多边形都是简单的,即其顶点各不相同,且除相邻边在公共顶点处接触外,多边形的任意两条边均不相交或接触。不同的岛屿之间互不相交或接触。

输入最后包含另外 $m$ 行,每行描述一条飞行路径。每行包含六个整数 $x_1, y_1, z_1, x_2, y_2, z_2$ ($|x_i|, |y_i|, |z_i| \le 10^6, z_i > 0$ 且 $(x_1, y_1) \neq (x_2, y_2)$)。它们指定了一次从 $(x_1, y_1, z_1)$ 到 $(x_2, y_2, z_2)$ 的飞行。

输出格式

输出能够使给定航班完整测量所有岛屿的最小角度 $\theta$(以度为单位)。答案应精确到 $10^{-6}$ 的绝对或相对误差。如果不存在这样的角度,则输出 impossible。输入数据的选择保证了如果岛屿顶点的坐标改变不超过 $\pm 10^{-8}$,则答案的变化不会超过允许的舍入误差。

样例

样例输入 1

3 2
3
20 30
50 50
10 50
4
40 20
60 10
75 20
60 30
4
45 60
55 55
60 60
55 65
0 30 20 78 70 5
55 0 20 70 60 10

样例输出 1

48.031693036

样例输入 2

1 1
4
0 0
10 0
10 10
0 10
5 5 10 15 5 10

样例输出 2

impossible

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.