QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#2223. 疯狂钻石

Statistics

火星缺乏全球磁场。先进的装置可以探测微弱的局部磁场,并作为导航指南针使用。

这种指南针依赖于装置内部复杂迷宫中一颗高磁性钻石晶体的运动。由于其运动的复杂性,这颗晶体通常被称为“疯狂钻石”(Mad Diamond)。

指南针迷宫建立在一个位于平面圆盘上的同心圆环系统上,圆盘边缘有一个所谓的基准点。每个圆环上都有 360 个等间距的所谓主点。主点的角度是两条特定射线之间的夹角,以度为单位测量。第一条射线从迷宫中心指向基准点,第二条射线从迷宫中心指向主点。圆环上第一个主点的角度为 $0^\circ$,顺时针方向下一个主点的角度为 $1^\circ$,依此类推。

迷宫本身由圆弧段和直线径向段组成。圆弧段总是完全嵌入在其中一个圆环中。它始于一个主点,也终于一个主点。每个径向段连接两个相邻的圆环,并且垂直于连接点处圆环的切线。通常,径向段的至少一个端点也属于一个圆弧段,但这并非严格要求。任意两条线段只能在主点处相交。没有任何两条线段重叠,哪怕是部分重叠。

在开始校准指南针之前,给定迷宫中的两个点:主起点和主终点。钻石位于主起点。钻石必须从主起点出发,沿着迷宫中的线段移动,最终停在主终点。

在校准过程中,指南针垂直悬挂在墙上,基准点最初位于指南针的顶部。校准分阶段进行。在每个阶段,指南针保持固定,钻石穿过迷宫,从其先前的位置落到迷宫中当前可到达的最低点。当钻石停止时,该阶段结束。如果钻石在迷宫中的位置阻碍了其移动,它也可能在阶段中保持静止。在每两个连续阶段之间,指南针顺时针或逆时针旋转 $1^\circ$。

大多数情况下,由于迷宫的形状,钻石无法完全垂直移动。在任何时间点,钻石的运动矢量与垂直矢量的偏差最多为 $89^\circ$。注意,在每个阶段结束时,钻石都位于某个主点。

当钻石到达一个有两条线段继续向下延伸的主点时,它总是会检查径向段。如果通过径向段的当前钻石运动矢量与垂直方向的偏差最多为 $45^\circ$,则钻石会落入该线段并继续向下移动。否则,钻石将继续其在圆弧段上的当前运动。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 20$),表示迷宫中圆环的数量。

接下来有 $N$ 对行。每一对行描述一个圆环,按从迷宫中心向外的顺序排列(圆环编号为 $0, 1, \dots, N-1$)。每一对中的第一行以数字 $K$ 开头,表示当前圆环上迷宫圆弧段的数量。随后是 $K$ 对数字 ($X$ 和 $Y$),表示一条圆弧,其起点为角度为 $X$ 的主点,终点为角度为 $Y$ 的主点。每一对中的第二行包含整数 $L$,表示从当前圆环通往下一个圆环的径向段数量。随后是 $L$ 个值,表示径向段所在的主点角度。

最后两行输入分别表示主起点和主终点。每个点由它所在的圆环编号和它重合的主点角度来描述。

输出格式

输出使钻石从主起点到达主终点所需的阶段之间最少的指南针旋转次数。钻石必须在最后一个阶段结束时静止在主终点。如果钻石无法在任何阶段结束时到达主终点,则输出字符串 “Impossible”。

样例

输入格式 1

3
2 30 80 90 140
2 45 110
2 0 60 90 180
1 30
1 30 140
0
0 30
2 140

输出格式 1

260

Sample input 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.