logo AlgoBeat OnlineJudge
登录 注册

#102279. [BZOJ 2279] [Ncpc2010]Around the track

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给你一个图。你找一条欧拉回路出来,使得沿这条路转过的角度最小。

图很特殊,一个结点出来,要么恰好有 条边,或者恰好有 条边。

一个欧拉回路,即它必须遍历每个图形的边恰好一次,并回到起点(输入的跑道保证其欧拉回路的存在)。

总的转弯弧度就是在这个回路中, 在每个结点处需要的转弯弧度的总和,在一条直线上继续行进不用转弯。

每一段跑道都是可以双向行驶的。

输入格式

第一行两个整数 ,分别表示点数和边数。

接下来 行,依次组出每个结点的坐标 ,每个结点的坐标是唯一的。

接下来 行,每行两个数 ,表示存在边 (结点从 开始编号)。

输出格式

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

样例

样例输入 #1

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

样例输出 #1

37.699111843077446

数据范围与提示

对于 的数据,