你可能从未听说过 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