← 返回题目列表

AtCoder · yuha_c83_05

E. 相机控制 - 相机控制

中文机器翻译题面 查看原题

問題文

“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 积分

入力例 1

1
0 0
1
10 10 0
1
0 1

出力例 1

1.00000000000000000000

入力例2

2
0 0
1
10 10 0
1
0 1
1
20 20 0
1
1 2

出力例 2

2.00000000000000000000

入力例 3

2
0 0
1
10 10 0
1
0 1
1
-10 10 0
1
1 2

出力例 3

1.00000000000000000000

入力例 4

2
0 0
2
-5 5 0
5 5 10
1
0 6
2
5 5 0
-5 5 10
1
6 10

出力例 4

9.00000000

入力例 5

1
7 -65
2
-65 10 0
65 1 3
2
0 1
23 24

出力例 5

2.00000000

入力例 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

出力例 6

5.98862017