网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
线型网络
成绩 | 0 | 开启时间 | 2013年01月16日 星期三 09:10 |
折扣 | 0.8 | 折扣时间 | 2013年01月16日 星期三 09:10 |
允许迟交 | 是 | 关闭时间 | 2013年01月16日 星期三 09:10 |
输入文件 | linec.in | 输出文件 | linec.out |
【问题描述】
有 N ( <=20 ) 台 PC 放在机房内,现在要求由你选定一台 PC,用共 N-1 条网线从这台机器开始一台接一台地依次连接他们,最后接到哪个以及连接的顺序也是由你选定的,为了节省材料,网线都拉直。求最少需要一次性购买多长的网线。(说白了,就是找出 N 的一个排列 P1 P2 P3 ..PN 然后 P1 -> P2 -> P3 -> ... -> PN 找出 |P1P2|+|P2P3|+...+|PN-1PN| 长度的最小值)
【输入格式】
第一行 N ,下面 N 行,每行分别为机器的坐标(x,y) ( 实数 -100<=x,y<=100 )
【输出格式】
最小的长度,保留两位小数。
【输入样例】
3
0 0
1 1
1 -1
0 0
1 1
1 -1
【输出样例】
2.83