loj#P6857. 「ICPC World Finals 2021」俯瞰岛屿

「ICPC World Finals 2021」俯瞰岛屿

题目描述

你可能从未听说过 Iceepeecee 群岛,但这个群岛很适合他们的居民。群岛位于南太平洋的一个偏远地区,是真正的偏僻之地,没有任何固定的空中或海上航线。这个群岛一直是一个热带天堂,当地的动植物没有受到破坏。

当你不想被成群结队的游客包围时,离开地图是很好的选择,但当你因为某些原因确实需要地图时,就不那么理想了。最近就出现了一个需要地图的理由,Iceepeecee 的中央政府需要一张精确的岛屿地图来分配政府资金。即使是热带天堂也需要钱,所以 Iceepeecee 需要一张地图!

绘制地图的最简单方法是进行空中勘测。在因为包机太贵、制作探空气球太危险、给信鸽装上相机对动物太残忍而否定掉许多方案之后,他们有了一个绝妙的想法。即使岛屿的位置很偏僻,仍然有很多商业飞机在 Iceepeecee 的上空飞行。如果在已经安排好的航班上安装相机呢?这将是一个解决这个问题的廉价方案!

Iceepeecee 的计划是在飞机上安装线扫描相机。这些相机的镜头垂直指向下方,每次收集一条与飞行路径正交的线段上的图像。所拍摄的线段将由飞机飞行的高度和相机的光圈角度 θ\theta 决定(见图 F.1)。更大的角度 θ\theta 意味着相机可以拍到更多的东西,但也意味着相机的成本更高。

F1.png

图 F.1 飞机飞行的正视图。它的相机镜头指向下方,飞机下方可以看到的地面部分显示为绿色。能看到多少取决于光圈角度 θ。

此外,Iceepeecee 希望确保每个岛屿都至少被一个航班观察到其全部。这意味着一个岛屿被多个航班拍摄到它的部分照片是不够的,即使这些照片拼起来覆盖了整个岛屿。

飞行路线是在三维空间中的直线段,即 (x1,y1,z1)(x2,y2,z2)(x_1,y_1,z_1) - (x_2,y_2,z_2)(见图 F.2),其中 zz 坐标给出飞机的高度。照片只沿这些线段拍摄。

考虑到他们的岛屿和航线的位置,Iceepeecee 希望找到最小的光圈角度 θ\theta,以便能够成功进行勘测。你能帮忙吗?

输入格式

输入描述了一组岛屿和航线。第一行两个整数 nnm (1n,m100)m\ (1\le n,m\le 100),分别表示岛屿数和航线数。接下来描述这 nn 个岛屿,对于每个岛屿,第一行一个整数 ni (3ni100)n_i\ (3\le n_i\le 100),表示描述第 ii 个岛屿的多边形的顶点个数。接下来 nin_i 行,每行两个整数 xij,yij (xij,yij106)x_{ij},y_{ij}\ (|x_{ij}|,|y_{ij}|\le 10^6),表示第 ii 个岛屿的顶点,顶点按逆时针顺序给出。每个岛屿都是简单多边形,也就是说,它的顶点互不相同,并且除了相邻两边共顶点外,多边形没有两条边相交或共顶点。不同的岛屿互不相交或接触。

接下来 mm 行描述航线。每行六个整数 $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))$。表示一条从 (x1,y1,z1)(x_1,y_1,z_1)(x2,y2,z2)(x_2,y_2,z_2) 的航线。

输出格式

输出最小角度 θ\theta(角度制)满足在给定航线的情况下可以完成完整的勘测任务。你的答案与标准答案之间的绝对误差或相对误差不应大于 10610^{-6}。如果不存在这样的角度,输出 impossible。输入满足如果对岛屿的坐标改变最多 ±108\pm 10^{-8},答案的改变量不会比允许的舍入误差大。

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

48.031693036

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

impossible