UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2279. [Ncpc2010]Around the track

统计 下载数据

Description

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

Input

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开始编号)

Output

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

Sample Input

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

Sample Output

37.699111843077446

Hint

Source