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