1621. 电话局选址

单点时限: 2.0 sec

内存限制: 256 MB

在一个山区乡镇里,分布着若干个村庄 ($n<10$)。这个镇计划筹建一个电话模块网,在这一模块网中每个村庄被连接到一起,村庄与村庄之间只用一条电缆连接,并且除了首尾的两个村庄只分别连接着一个村庄外,其他的任一个村庄恰连接着两个村庄。图 1 给出了各个村庄的分布情况,图中已标出了各个村庄的坐标,连接各村庄的直线距离单位为千米。

你的任务是选择一个村庄作为电话模块网的起点,希望埋设的电缆线长度尽可能的短。

输入格式

输入文件由若干行数据序列组成,第一行,一个数据表示村庄的个数;第二行开始,每行两个数据,数据之间用一个或若干个空格隔开,用以表示每个村庄的坐标。镇中心的坐标即为坐标中心。

输出格式

输出结果的第一行为该电话模块网中起点村庄的坐标;以下第 $i$ 行数据是第 $i$ 个是村庄的坐标,最后一行是一个数据,即:耗用电缆长度的最小值。

样例

Input
5
-8 16
4 16
-8 11
0 0
21 5
Output
0 0
-8 11
-8 16
4 16
21 5
50.85

11 人解决,20 人已尝试。

16 份提交通过,共有 81 份提交。

6.6 EMB 奖励。

创建: 14 年,5 月前.

修改: 4 年前.

最后提交: 1 年,1 月前.

来源: N/A

题目标签