1546: 铺设管道
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:19
解决:15
题目描述
呆头父子承包了一个果园,计划铺设一条由东向西的输水主管道。该果园有n 棵果树。从每每棵都要有一条灌溉管道沿最短路经(或南或北)与主管道相连。如果给定n棵果树的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各果树到主管道之间的灌溉管道长度总和最小的位置?
编程任务:给定n棵果树的位置,计算个果树到主管道之间的灌溉管道最小长度总和。
输入
第一行为果树数量n,(1<=n<=10000)
接下来n行是果树的位置,每行2个整数,分别表示x和y坐标 -10000<=x,y<=10000
输出
输出为各果树到主管道之间的灌溉管道最小长度的总和
样例输入 复制
5
1 2
2 2
1 3
3 -2
3 3
样例输出 复制
6