4457: Monitoring Target
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
一名侦查员奉命监视一个可疑目标，目标在一片开阔区域内行走，由于受一些楼房等障碍物遮挡的影响，并不能时刻观察到目标。 现在侦查员通过其他高科技手段获取了目标行走的路径，他想知道在目标行走的这段时间里一共有多长时间能够看到目标？
在真实环境下，这一问题是十分复杂的。为了简化问题，我们将场景建立在2D平面上：目标匀速行走，每1个单位时间向前前进1个单位距离，走过的路径为折线；障碍物为简单多边形；侦查员固定在某一个点。你能计算出目标行走过程中侦查员一共有多长时间能够看到目标吗？我们认为侦查员能够看到目标，当且仅当侦查员和目标之间的连线不经过任何一个障碍物(包括障碍物的边及顶点)。
输入格式
输入包含不超过100组数据。 每组数据第一行为两个整数d, n(2 ≤ d ≤ 100, 1 ≤ n ≤ 10)，即目标行走的折线路径的顶点的数量和障碍物的数量。 接下来一行包含2d个整数x1, y1, x2, y2, …, xd, yd(0 < xi, yi < 1000, 1 ≤ i ≤ d)，依次描述了目标行走的折线路径上的各个顶点的坐标。 接下来2n行依次描述了各个障碍物。 对于每个障碍物，第一行为一个整数mj(3≤ mj ≤ 10)，即第j(1 ≤ j ≤ n)个障碍物的顶点的数量。 第二行为2mj个整数x1, y1, x2, y2, …, xmj, ymj(0 < xi, yi < 1000, 1 ≤ i ≤ mj)，按逆时针方向依次描述了该障碍物各个顶点的坐标。 每组数据最后一行为一个整数p(0 < p < 1000)，即侦查员的位置在(p, 0)。数据保证障碍物之间不会相交，目标行走过程中不会横穿障碍物，行走路径不会和障碍物的边缘重合，但有可能经过障碍物的顶点。
输出格式
对于每组数据，输出目标行走过程中侦查员能够观察到目标的时间长度，和标准输出之间的绝对误差不超过0.001即可。
输入样例 复制
5 1
1 5 6 5 6 1 2 1 2 6
4
5 4 3 4 3 2 5 2
3
4 1
1 2 5 2 4 1 5 1
3
2 1 4 1 3 2
3输出样例 复制
13.000000
1.000000