身可死,武士之名不可弃

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目描述

源氏:你好,我叫岛田源氏,请多多指教!

王木木:源氏大人,请问您最重要的能力是哪个呢?

源氏:(爬墙)当然是每当我杀死一个敌人,shift就能刷新啦

王木木:团战时,如何选择击杀顺序呢?

源氏:(当然是先杀对面的欧尼酱)选最近的杀,然后刷新shift接着杀穿对方。

王木木:(原来是幼儿源啊。。。)原来如此!

半藏:愚蠢的欧豆豆,快来做这道简单的几何学!

输入

多组输入数据

每组数据第一个数为敌人数量n(0<n<100)

接下来n行,每行为一个敌人的坐标x,y(x,y为正整数)

输出

每组数据输出源氏的最短击杀路径长度(保留两位小数)

规则

源氏的特别击杀顺序——

1 源氏从最左边切入,也就是说,源氏的第一个击杀目标为x最小的敌人

2 源氏严格地从左到右击杀敌人直至最右边的敌人,然后源氏严格地从右到左直至杀回出发点,即保证总最左点到最右点的路线,X单调递增,最右点到出发点最左点的返回路径中,X单调递减。

3 如果有两个敌人X相同,按Y递增的原则排序

4 重要——每个敌人必须且只能被击杀一次

输入样例

3
1 1
2 3
3 1
4
1 1
2 3
4 2
3 1

输出样例

6.47
7.89

相关推荐