#P17826. [Ontak2022]GOK
[Ontak2022]GOK
题目描述
赛道是两个简单多边形之间的区域:一个作为内墙,另一个作为外墙。内多边形完全位于外多边形内部,两者边界不相交也不接触。
你以恒定速度行驶,转弯时可以瞬间改变方向而不减速。求在赛道中绕内多边形一周的最短闭合曲线长度。路线可以沿着墙的边界行驶。
输入格式
第一行一个整数 ,表示内多边形顶点数。接下来 行,每行两个整数,表示一个顶点。
接着一行一个整数 ,表示外多边形顶点数。再接下来 行,每行两个整数,表示一个顶点。
两个多边形的顶点均按逆时针顺序给出。
输出格式
输出最短路线长度。绝对误差或相对误差至多 均可。
数据范围
;所有坐标为整数且在 内。两个多边形都是无自交的简单多边形,面积为正;允许连续顶点共线。两多边形边界不相交、不接触。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n+m≤12 | 26 |
| 2 | 外多边形为凸多边形 | 32 |
| 3 | 无额外限制 | 42 |
样例 1
输入:
3
1 1
2 1
1 2
3
0 0
4 0
0 4
输出:
3.414213562
样例 2
输入:
5
1 1
5 1
5 5
3 3
1 5
4
0 0
6 0
6 6
0 6
输出:
16.000000000
样例 3
输入:
5
1 1
5 1
5 5
3 3
1 5
5
0 0
6 0
6 6
3 4
0 6
输出:
16.472135955
说明
前两个样例分别得到三角形周长和内墙凸包周长;第三个样例的外墙向内凹陷,最短路线因此更长。