OpenJudge

02:油田

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
10240kB
描述

某石油公司计划建造一条由东向西的主输油管道。该输油管道要穿过一个有n个油井的油井,每中油井都要有一条输油管道(向南或向北)与主输油管道相连。给出n个油井的位置,即它们的X坐标Y坐标(X轴、Y轴分别平行于主输油管道和输油管道),如何确定主管道的位置,使各油井到主输油管道的输油管道长度总和最小?

(n<=10000,各坐标值为不大于1000的正整数)<=1000000,10000<=1000000,10000<=1000000,10000<=10000,各坐标值为不大于1000的正整数)<=10000,各坐标值为不大于1000的正整数)<=1000000,10000<=10000,各坐标值为不大于1000的正整数)

输入
第一行一个整数:n
从第二行开始共n行,每行两个整数,分别为每个油井的坐标:x y
输出
一个整数,最小的输油管道总和。
样例输入
2
1 2
2 -1
样例输出
3
全局题号
4321
添加于
2011-12-09
提交次数
25
尝试人数
4
通过人数
1