F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1137. -- [POI2009]Wsp 岛屿

1137: [POI2009]Wsp 岛屿

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 351  Solved: 163
[Submit][Status][Discuss]

Description

Byteotia岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号1到n。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了,不能走,但是可以经过这条道路与未被控制的道路的交点。问从城市1到n的最短距离。

Input

第一行正整数n m表示城市数和被控制的岛屿数(3≤n≤10^5 1≤m≤10^6)接下来n行每行两个整数x y表示每个城市的坐标。(|x|,|y|≤10^6)接下来m行描述一条不能走的道路(起点和终点)。数据保证有解。

Output

输出一个实数,最短距离,误差10^-5以内均算正确。

Sample Input

6 9
-12 -10
-11 6
-4 12
6 14
16 6
18 -2
3 4
1 5
2 6
2 3
4 5
3 5
1 3
3 6
1 6

Sample Output

42.000000000

HINT

Source

鸣谢 vfleaking

[Submit][Status][Discuss]

HOME Back