#P17826. [Ontak2022]GOK

[Ontak2022]GOK

题目描述

赛道是两个简单多边形之间的区域:一个作为内墙,另一个作为外墙。内多边形完全位于外多边形内部,两者边界不相交也不接触。

你以恒定速度行驶,转弯时可以瞬间改变方向而不减速。求在赛道中绕内多边形一周的最短闭合曲线长度。路线可以沿着墙的边界行驶。

输入格式

第一行一个整数 nn,表示内多边形顶点数。接下来 nn 行,每行两个整数,表示一个顶点。

接着一行一个整数 mm,表示外多边形顶点数。再接下来 mm 行,每行两个整数,表示一个顶点。

两个多边形的顶点均按逆时针顺序给出。

输出格式

输出最短路线长度。绝对误差或相对误差至多 10−610^{-6} 均可。

数据范围

3≤n,m≤503\le n,m\le50;所有坐标为整数且在 [−5000,5000][-5000,5000] 内。两个多边形都是无自交的简单多边形,面积为正;允许连续顶点共线。两多边形边界不相交、不接触。

子任务

子任务 附加限制 分值
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

说明

前两个样例分别得到三角形周长和内墙凸包周长;第三个样例的外墙向内凹陷,最短路线因此更长。