問題文
“ACM48”是日本备受关注的舞蹈声乐组合。
这个冬天,ACM48将进行世界巡演,而你将作为该巡演的摄影师工程师参与其中。
你的角色是编写安装在舞台上的相机控制程序。
出于简便,假设舞台位于二维坐标上。 相机可以360度自由旋转,但无法移动位置。
在舞台表演期间,ACM48的每位成员都会按照预先决定的移动路线行动,并演唱分配给自己的部分。在这里,成员的移动路线被假定为折线。
你控制的摄像机在舞台表演期间,只能聚焦于一名成员。此外,仅当从摄像机方向看,有多名成员位于同一方向时,才能在这些成员之间自由切换摄像机的焦点。(如果有多名成员位于从摄像机延伸出的半直线上,可以选择聚焦在离摄像机较远的成员。)即便曾经聚焦于已经唱完歌的歌手,也只能在该成员所在的半直线上没有其他成员的情况下,无法将摄像机的焦点转移到其他成员。
你的工作是编写一个程序,当舞台表演的流程被给出时,求出能够将焦点集中在正在唱歌的成员身上的最长时间。
在解决问题时,可以假设满足以下条件。
- 在舞台表演开始时,可以将摄像机的焦点对准任意成员。
- 每个成员的移动路线不会触碰到摄像机。
- 每个成员到达移动路线的终点后,会停留在该位置。
入力
输入格式如下。
N
c_{x} c_{y}
MEMBER\_INFORMATION\_1
MEMBER\_INFORMATION\_2
...
MEMBER\_INFORMATION\_N
N
(
1 ≤ N ≤ 50
)表示成员的数量,
(c_{x}, c_{y})
表示摄像机的坐标。 接下来
N
会给出人员的信息。
i
第 n 个成员的信息格式如下。
M_{i}
x_{i,1} y_{i,1} t_{i,1}
...
x_{i,M_{i}} y_{i,M{i}} t_{i,M_{i}}
L_{i}
b_{i,1} e_{i,1}
...
b_{i,L_{i}} e_{i,L_{i}}
M_{i}
(1 ≤ M_{i} ≤ 100)
表示路线上的顶点数量,
(x_{i,j}, y_{i,j})
是
您也可以写
j
第 i 个顶点的坐标。
t_{i,j}
(0 = t_{i,0} < t_{i,j} < t_{i,j+1} ≤ 10^{3})
是
您也可以写
i
号成员到达
j
号顶点的时间,
L_{i}
(0 ≤ L_{i} ≤ 100)
是
您也可以写
i
号成员演唱的声乐部分数量,
b_{i,k}
和
按以下格式输出
e_{i,k}
(0 ≤ b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1}
≤ 10^{3})
是
您也可以写
k
号声乐部分的开始时间和结束时间。
输入中的所有值都是整数。此外,输入中所有坐标的绝对值为
10^{3}
下面。
出力
输出能够将焦点集中在正在唱歌的成员上的最大时间。输出中
10^{-6}
不得包含超过的绝对或相对误差。
部分点
- M_{i} = 1 的输入给出正确答案,则部分点为 125
积分
入力例2
2
0 0
1
10 10 0
1
0 1
1
20 20 0
1
1 2
入力例 3
2
0 0
1
10 10 0
1
0 1
1
-10 10 0
1
1 2
入力例 4
2
0 0
2
-5 5 0
5 5 10
1
0 6
2
5 5 0
-5 5 10
1
6 10
入力例 5
1
7 -65
2
-65 10 0
65 1 3
2
0 1
23 24
入力例 6
2
0 0
2
100 10 0
-10 10 10
5
0 1
2 3
4 5
6 7
8 9
2
10 0 0
0 10 10
5
1 2
3 4
5 6
7 8
9 10