Toggle navigation
New Online Judge
常见问答
问题
来源/分类
状态
排名
竞赛&作业
近期比赛
Login
问题1099--输油管道问题
1099: 输油管道问题
时间限制:
1
Sec
内存限制:
256 MB
提交:
26
解决:
17
[
状态
] [
提交
] [命题人:
]
题目描述
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。
从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。
如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向)
应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置
输入
输入第一行为正整数n(1<=n<=10000)
接下来n行,每行两个整数x,y,表示第i个油井的位置(-10000<=x,y<=10000)
输出
输出一行整数表示答案
样例输入
Copy
5 1 2 2 2 1 3 3 -2 3 3
样例输出
Copy
6
来源/分类
基础题
排序