1110 : Monitoring Target

Description

一名侦查员奉命监视一个可疑目标，目标在一片开阔区域内行走，由于受一些楼房等障碍物遮挡的影响，并不能时刻观察到目标。 现在侦查员通过其他高科技手段获取了目标行走的路径，他想知道在目标行走的这段时间里一共有多长时间能够看到目标？

在真实环境下，这一问题是十分复杂的。为了简化问题，我们将场景建立在2D平面上：目标匀速行走，每1个单位时间向前前进1个单位距离，走过的路径为折线；障碍物为简单多边形；侦查员固定在某一个点。你能计算出目标行走过程中侦查员一共有多长时间能够看到目标吗？我们认为侦查员能够看到目标，当且仅当侦查员和目标之间的连线不经过任何一个障碍物(包括障碍物的边及顶点)。

Input

输入包含不超过100组数据。 每组数据第一行为两个整数d, n(2 ≤ d ≤ 100, 1 ≤ n ≤ 10)，即目标行走的折线路径的顶点的数量和障碍物的数量。 接下来一行包含2d个整数x₁, y₁, x₂, y₂, …, x_d, y_d(0 < x_i, y_i < 1000, 1 ≤ i ≤ d)，依次描述了目标行走的折线路径上的各个顶点的坐标。 接下来2n行依次描述了各个障碍物。 对于每个障碍物，第一行为一个整数m_j(3≤ m_j ≤ 10)，即第j(1 ≤ j ≤ n)个障碍物的顶点的数量。 第二行为2m_j个整数x₁, y₁, x₂, y₂, …, x_mj, y_mj(0 < x_i, y_i < 1000, 1 ≤ i ≤ m_j)，按逆时针方向依次描述了该障碍物各个顶点的坐标。 每组数据最后一行为一个整数p(0 < p < 1000)，即侦查员的位置在(p, 0)。数据保证障碍物之间不会相交，目标行走过程中不会横穿障碍物，行走路径不会和障碍物的边缘重合，但有可能经过障碍物的顶点。

Output

对于每组数据，输出目标行走过程中侦查员能够观察到目标的时间长度，和标准输出之间的绝对误差不超过0.001即可。

Sample

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

Hint

Source

Author

Staginner