#P16673. [Ctu2021]Mad Diamond
[Ctu2021]Mad Diamond
题目描述
火星没有全球性的磁场。某些先进装置能够检测微弱的局部磁场,并作为导航罗盘使用。
这种罗盘依靠一颗强磁化的钻石晶体在装置内部的复杂迷宫中运动。由于它的运动看起来非常复杂,人们通常称它为“疯狂钻石”。
罗盘迷宫位于一个平面圆盘上,由若干同心圆环组成。圆盘边缘有一个固定的基准点。
每个圆环上均匀分布着 个主点。主点的角度定义如下:
- 从迷宫中心指向基准点的射线作为第一条射线;
- 从迷宫中心指向该主点的射线作为第二条射线;
- 两条射线之间按顺时针方向测得的角度,就是该主点的角度。
因此,每个圆环上的主点角度依次为
迷宫由两类线段组成:
- 圆弧段:完全位于某一个圆环上,起点和终点均为主点;
- 径向段:连接相邻两个圆环,并在连接处垂直于圆环的切线。
径向段的一个或两个端点可能同时位于圆弧段上,但这不是强制要求。
任意两条迷宫线段只能在主点处相交,并且任意两条线段都不会发生长度为正的重叠。
校准开始前,给定迷宫中的一个起始主点和一个终止主点。钻石最初位于起始主点,它需要沿迷宫线段运动,并最终停在终止主点。
校准分为若干阶段。
在每个阶段中:
- 罗盘保持静止;
- 钻石在重力作用下沿迷宫移动;
- 它会一直移动到当前能够到达的最低位置;
- 当钻石停止后,本阶段结束。
如果当前位置阻止钻石继续运动,它也可能在某个阶段中完全不动。
在两个连续阶段之间,可以把罗盘顺时针或逆时针旋转 。
校准开始时,基准点位于罗盘最上方。
受迷宫形状限制,钻石通常无法严格竖直下落。钻石运动方向与竖直向下方向之间的夹角在任何时刻都不能超过 。
每个阶段结束时,钻石一定停在某个主点上。
如果钻石到达一个主点,并且从该点出发当前有两条线段都向下延伸,它会优先检查径向段:
- 若沿径向段运动时,与竖直向下方向的夹角不超过 ,钻石就进入径向段;
- 否则,它继续沿当前圆弧方向运动。
请计算为了让钻石最终静止在终止主点,至少需要把罗盘旋转多少度。
输入格式
第一行包含一个整数 :
表示迷宫中的圆环数量。圆环从内到外编号为
接下来有 组描述,每组包含两行,按圆环从内到外的顺序给出。
每组的第一行首先包含一个整数 ,表示当前圆环上的圆弧段数量。随后包含 对整数 ,表示一条圆弧从角度为 的主点开始,到角度为 的主点结束。
每组的第二行首先包含一个整数 ,表示从当前圆环向外连接到下一个圆环的径向段数量。随后包含 个角度,表示这些径向段所在的主点。
最外层圆环不会再向外连接其他圆环,因此其径向段数量可以为 。
最后两行分别描述起始主点和终止主点。每个点由两个整数表示:
- 所在圆环编号;
- 主点角度。
输出格式
输出一个整数,表示在各阶段之间所需旋转的最小总角度。
最后一个阶段结束时,钻石必须静止在终止主点上,而不能只是经过该点。
如果无论如何都无法让钻石在某个阶段结束时停在终止主点,输出:
Impossible
样例
输入
3
2 30 80 90 140
2 45 110
2 0 60 90 180
1 30
1 30 140
0
0 30
2 140
输出
260
图示
