#2279. [Ncpc2010]Around the track

题目描述

给你一个图。你找一条欧拉回路出来，使得沿这条路转过的角度最小。
图很特殊，一个结点出来，要么恰好有2条边，或者恰好有4边
一个欧拉回路，即它必须遍历每个图形的边恰好一次，并回到起 点。 （输入的跑道保证其欧拉回路的存在）.总的转弯弧度就是在这个回路中， 在每个结点处需要的转弯弧度的总和，在一条直线上继续行进不用转弯。每一段 跑道都是可以双向行驶的。

输入格式

Oneline with 3 < = N < = 10000{the number of nodes{and N < = M < = 2N {the number
of edges.
N lines with the x and y coordinates o feachnode,inorder.0 < = x;y < = 10000.The nodes
have unique coordinate pairs.
M lines with two space separated numbers i and j,denoting an edge between nodes i and
j.The nodes are 0-indexed.

第一行 两个数,N , M . (3<=N <=10000, 代表结点的个数。N<=M<=2N 边的个数)
接下来N行，依次组出每个结点的坐标 0<=x,y<=10000 。每个结点的坐标是唯一 的
接下来M行,每两个数，表示i, j之间存在一条边.(结点从0开始编号)

输出格式

欧拉回路上最小的所需转弯的弧度和

样例

样例输入

12 19  

1077 2677  

7473 4262  

1095 8844  

84 7875  

7241 7320  

9143 4888  

4524 1947  

4652 1260  

3503 7882  

4692 223  

9745 5245  

2037 2387  

0 1  

0 2  

1 4  

1 2  

1 3  

3 4  

4 6  

4 5  

5 8  

5 6  

5 7  

6 8  

6 7  

7 9  

7 8  

8 9  

9 11  

9 10  

10 11  

样例输出

37.699111843077446  

数据范围与提示