P9444 [ICPC 2021 WF] Islands from the Sky

你可能从未听说过 Iceepeecee 群岛，但这正是他们的居民所希望的。位于南太平洋的一个偏远地区，它们真正远离人迹罕至的地方，没有任何定期的空中或海上交通，仍然是一个未受破坏的热带天堂，拥有未受破坏的当地动植物。 当你不想被成群的游客淹没时，远离地图是很好的，但当你确实需要地图时就不太理想了。最近出现了一个这样的原因：Iceepeecee 的中央政府需要一个精确的岛屿地图来分配政府资金。即使是热带天堂也需要钱，所以 Iceepeecee 需要一张地图！ 创建地图的最简单方法是航空测量。在认为包机太贵、建造气球太危险、给信鸽装上相机对动物太残忍之后，他们有了一个绝妙的主意。即使在这个偏远的地方，仍然有很多商业飞机飞过 Iceepeecee 上空。如果在已经计划飞行的航班上安装相机呢？这将是一个解决问题的廉价方案！ Iceepeecee 的计划是在飞机上安装线扫描相机。这些相机垂直向下拍摄，每次收集一条线段的图像，与飞行路径正交。拍摄的线段将由飞机的飞行高度和相机的光圈角度 $\theta$ 决定（见图 F.1）。更大的角度 $\theta$ 意味着相机可以看到更多，但也意味着相机更贵。 此外，Iceepeecee 希望确保每个岛屿都能被至少一次航班完整观察到。这意味着不够仅仅通过多次航班部分拍摄到一个岛屿，即使这些照片的组合覆盖了整个岛屿。 图 F.1：飞机的正面视图。其相机向下拍摄，可以看到飞机下方的绿色部分。可见的范围取决于光圈角度 $\theta$。 飞行路径在三维空间中沿直线段，即 ($x_1, y_1, z_1$) $-$ ($x_2, y_2, z_2$)（见图 F.2），其中 $z$ 坐标给出飞机的高度。照片仅在这些线段上拍摄。 给定他们的岛屿和航班的位置，Iceepeecee 想要找到允许成功测量的最小光圈角度 $\theta$。你能帮忙吗？ 图 F.2：三个岛屿（以黑色显示）和两条飞行路径（红色和绿色）。未显示高度。阴影区域表示在最佳选择的 $\theta$ 下两条飞行路径上可见的地面。这对应于第一个样例输入。

输入描述了一组岛屿和飞行路径。首先是一行包含两个整数 $n$ 和 $m$，分别表示岛屿的数量 $n$ 和飞行路径的数量 $m$（$1 \leq n,m \leq 100$）。接下来是 $n$ 个岛屿的描述。每个岛屿描述以一行开始，包含一个整数 $n_i$，表示描述第 $i$ 个岛屿的多边形的顶点数（$3 \leq n_i \leq 100$）。接下来是 $n_i$ 行，每行包含两个整数 $x_{ij}$，$y_{ij}$（$|x_{ij}|, |y_{ij}| \leq 10^6$），按逆时针顺序指定第 $i$ 个岛屿的顶点。每个岛屿的多边形是简单的，即其顶点是不同的，且多边形的边不相交或接触，除了相邻的边在其公共顶点处接触。不同的岛屿不相交或接触。 输入以另外 $m$ 行结束，每行描述一条飞行路径。每行包含六个整数 $x_1$，$y_1$，$z_1$，$x_2$，$y_2$，$z_2$（$|x_i|, |y_i|, |z_i| \leq 10^6$，$z_i > 0$ 且 ($x_1, y_1$) $ eq$ ($x_2, y_2$)）。它们指定了一次从 ($x_1, y_1, z_1$) 到 ($x_2, y_2, z_2$) 的飞行。

输出允许使用给定航班对岛屿进行完整测量的最小角度 $\theta$（以度为单位）。答案应精确到绝对或相对误差 $10^{-6}$。如果没有这样的角度，则输出 $\texttt{impossible}$。输入被选择为，如果岛屿顶点的坐标最多改变 $\pm 10^{-8}$，则答案不会超过允许的舍入误差。

题面翻译由 ChatGPT-4o 提供。