D. Dire Strait
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mickey has been enjoying sailing on the local lake, but now it's the end of the day and it's time to go back to dock to return the rental boat on time.

Find the shortest path from its current location to the one remaining egress point over water, staying within or passing along the coastline of the lake.

The lake is represented as a simple, potentially concave, polygon having vertices at integer coordinates, and with no $$$3$$$ consecutive vertices being collinear.

A triangulation of the lake into $$$(n-2)$$$ pieces is also provided.

Illustration of Sample Input 1.

Input
  • The number of vertices in the polygon representing the lake, $$$n$$$ ($$$3 \le n \le 100\,000$$$), and the indices of the two vertices between which to travel, $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n; a \ne b$$$).
  • $$$n$$$ further lines, each giving integer coordinates $$$x_i$$$ $$$y_i$$$ of the $$$i$$$th vertex of the polygon ($$$-10^9 \le x, y \le 10^9$$$) in anti-clockwise order.
  • $$$(n-2)$$$ further lines giving a triangulation of the lake. Each line specifies the $$$1$$$-based indices of three vertices $$$u$$$ $$$v$$$ $$$w$$$ (in anti-clockwise order).

The given triangles correspond to the polygon, thus cover the lake without any self-overlaps, holes, or other hazards.

Output

Output the shortest distance from point $$$a$$$ to point $$$b$$$ without exiting the lake.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
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
Output
18.246211251
Input
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
Output
5.6568542495