#P18567. [ukiepc2026]Dire Strait

[ukiepc2026]Dire Strait

Dire Strait

题目描述

米奇正在湖上驾船。现在已到归还租赁船只的时间,他需要尽快驶向湖边的指定出口。

湖面由一个简单多边形表示,允许是凹多边形。船可以在湖内部行驶,也允许沿湖岸线行驶,但不能离开湖面范围。起点和终点均是该多边形的顶点。

此外,输入还给出了这个多边形的一个完整三角剖分:将湖面恰好划分成 n−2n-2 个三角形,三角形之间没有面积重叠,也没有遗漏。

求起点到终点在湖面内的最短欧几里得路径长度。

图示(重绘示意图)

图 D.1:样例 1 的湖岸多边形、起点、终点与最短路径。

图 D.1:样例 1 的湖岸多边形、起点、终点与最短路径。 本图为重绘示意图。

输入格式

第一行输入三个整数 n,a,bn,a,b,分别表示湖岸多边形的顶点数、起点顶点编号和终点顶点编号。

接下来的 nn 行,每行输入两个整数 xi,yix_i,y_i,按逆时针方向依次给出多边形顶点坐标。顶点编号为 11 到 nn。

接下来的 n−2n-2 行,每行输入三个整数 u,v,wu,v,w,表示三角剖分中的一个三角形的三个顶点编号,三个顶点也按逆时针方向给出。

输出格式

输出一个实数,表示从顶点 aa 到顶点 bb 且始终不离开湖面的最短路径长度。

答案的绝对误差或相对误差不超过 10−610^{-6} 即可。

样例 #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

数据范围与保证

  • 3≤n≤1000003\le n\le100000;
  • 1≤a,b≤n1\le a,b\le n 且 a≠ba\ne b;
  • −109≤xi,yi≤109-10^9\le x_i,y_i\le10^9,坐标为整数;
  • 湖岸是一个简单多边形,顶点按逆时针排列;
  • 不存在连续三个共线的多边形顶点;
  • 给定三角剖分完全覆盖湖面,三角形没有面积重叠、不存在孔洞,且三角形顶点按逆时针排列。