#P18567. [ukiepc2026]Dire Strait
[ukiepc2026]Dire Strait
Dire Strait
题目描述
米奇正在湖上驾船。现在已到归还租赁船只的时间,他需要尽快驶向湖边的指定出口。
湖面由一个简单多边形表示,允许是凹多边形。船可以在湖内部行驶,也允许沿湖岸线行驶,但不能离开湖面范围。起点和终点均是该多边形的顶点。
此外,输入还给出了这个多边形的一个完整三角剖分:将湖面恰好划分成 个三角形,三角形之间没有面积重叠,也没有遗漏。
求起点到终点在湖面内的最短欧几里得路径长度。
图示(重绘示意图)

图 D.1:样例 1 的湖岸多边形、起点、终点与最短路径。 本图为重绘示意图。
输入格式
第一行输入三个整数 ,分别表示湖岸多边形的顶点数、起点顶点编号和终点顶点编号。
接下来的 行,每行输入两个整数 ,按逆时针方向依次给出多边形顶点坐标。顶点编号为 到 。
接下来的 行,每行输入三个整数 ,表示三角剖分中的一个三角形的三个顶点编号,三个顶点也按逆时针方向给出。
输出格式
输出一个实数,表示从顶点 到顶点 且始终不离开湖面的最短路径长度。
答案的绝对误差或相对误差不超过 即可。
样例 #1
输入
8 3 7
0 0
10 0
10 2
2 2
2 4
10 4
10 6
0 6
1 2 3
1 3 4
1 4 8
4 5 8
5 7 8
5 6 7
输出
18.246211251
样例 #2
输入
14 1 9
-3 -1
-1 -1
-1 -3
1 -3
1 -1
3 -1
3 1
1 1
1 3
5 3
5 5
-1 5
-1 1
-3 1
1 2 14
6 8 13
3 4 5
9 12 13
8 9 13
6 13 14
2 5 14
5 6 14
10 11 12
2 3 5
9 10 12
6 7 8
输出
5.6568542495
数据范围与保证
- ;
- 且 ;
- ,坐标为整数;
- 湖岸是一个简单多边形,顶点按逆时针排列;
- 不存在连续三个共线的多边形顶点;
- 给定三角剖分完全覆盖湖面,三角形没有面积重叠、不存在孔洞,且三角形顶点按逆时针排列。