loj#P6857. 「ICPC World Finals 2021」俯瞰岛屿
「ICPC World Finals 2021」俯瞰岛屿
题目描述
你可能从未听说过 Iceepeecee 群岛,但这个群岛很适合他们的居民。群岛位于南太平洋的一个偏远地区,是真正的偏僻之地,没有任何固定的空中或海上航线。这个群岛一直是一个热带天堂,当地的动植物没有受到破坏。
当你不想被成群结队的游客包围时,离开地图是很好的选择,但当你因为某些原因确实需要地图时,就不那么理想了。最近就出现了一个需要地图的理由,Iceepeecee 的中央政府需要一张精确的岛屿地图来分配政府资金。即使是热带天堂也需要钱,所以 Iceepeecee 需要一张地图!
绘制地图的最简单方法是进行空中勘测。在因为包机太贵、制作探空气球太危险、给信鸽装上相机对动物太残忍而否定掉许多方案之后,他们有了一个绝妙的想法。即使岛屿的位置很偏僻,仍然有很多商业飞机在 Iceepeecee 的上空飞行。如果在已经安排好的航班上安装相机呢?这将是一个解决这个问题的廉价方案!
Iceepeecee 的计划是在飞机上安装线扫描相机。这些相机的镜头垂直指向下方,每次收集一条与飞行路径正交的线段上的图像。所拍摄的线段将由飞机飞行的高度和相机的光圈角度 决定(见图 F.1)。更大的角度 意味着相机可以拍到更多的东西,但也意味着相机的成本更高。
此外,Iceepeecee 希望确保每个岛屿都至少被一个航班观察到其全部。这意味着一个岛屿被多个航班拍摄到它的部分照片是不够的,即使这些照片拼起来覆盖了整个岛屿。
飞行路线是在三维空间中的直线段,即 (见图 F.2),其中 坐标给出飞机的高度。照片只沿这些线段拍摄。
考虑到他们的岛屿和航线的位置,Iceepeecee 希望找到最小的光圈角度 ,以便能够成功进行勘测。你能帮忙吗?
输入格式
输入描述了一组岛屿和航线。第一行两个整数 和 ,分别表示岛屿数和航线数。接下来描述这 个岛屿,对于每个岛屿,第一行一个整数 ,表示描述第 个岛屿的多边形的顶点个数。接下来 行,每行两个整数 ,表示第 个岛屿的顶点,顶点按逆时针顺序给出。每个岛屿都是简单多边形,也就是说,它的顶点互不相同,并且除了相邻两边共顶点外,多边形没有两条边相交或共顶点。不同的岛屿互不相交或接触。
接下来 行描述航线。每行六个整数 $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))$。表示一条从 到 的航线。
输出格式
输出最小角度 (角度制)满足在给定航线的情况下可以完成完整的勘测任务。你的答案与标准答案之间的绝对误差或相对误差不应大于 。如果不存在这样的角度,输出 impossible
。输入满足如果对岛屿的坐标改变最多 ,答案的改变量不会比允许的舍入误差大。
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