XUT新生军训的时候,学生们要被训练的哭了。大家都知道,军训是一件枯燥并且很耗费体力的事情。刚入学的萌新对大学生活充满了期待,结果却被军训泼了一盆冷水。
这时候辅导员着急呀,这不能把学生整自闭了,这后面学习也会提不起精神,辅导员突然想到一个点子让学生娱乐娱乐。那就是训练一下教官。
这个点子就是躲猫猫,学生藏在学校的任何地方,教官需要找到自己所带的所有学生。但谁知教官偷偷加入了班级群,在学生藏好之后,教官突然在群里发了一个领福利的小游戏。学生藏起来之后就没有事情干了,看到这个游戏就全下载玩了起来。可是这个游戏会后台发送定位给教官,相当于教官是知道他们在哪藏着的。这是教官只需要一个一个走到他们藏身的地方,把他们带出来就好了。
为了方便数据的输入,学校可以看做一个二维平面图,教官在原点(0,0)作为出发点,而所有学生的藏身之处会处于任一象限。
这时教官又不满足了(教官每次走得都是直线),他想用最短的路径来把所有的学生都带出来,你可以帮帮教官完成这个任务吗?
输入第一行包括一个整数n,表示有n名学生。
n小于10,坐标大小在-100到100内接下来n行,每一行有两个整数x,y。表示的是这个学生所处的坐标(x,y)
输出一个数,代表教官需要找出所有学生的最短路径和(输出保留两位小数)。