管道铺设

管道铺设pipe.pas

【问题描述】

石油公司计划建造一条由南向北的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或东或西)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,使各油井到主管道之间的输油管道长度总和最小。现在给定n 口油井的位置,请计算各油井到主管道之间的输油管道最小长度总和。

【输入格式】pipe.in

文件的第1行是油井数n,1≤n≤10000。

接下来n行是油井的位置,每行2个整数x和y,-10000≤x,y≤10000。

【输出格式】pipe.out

只有一个数,表示油井到主管道之间的输油管道最小长度总和。

【样例输入】

5

2 1

2 2

3 1

-2 3

3 3

【样例输出】

6

原文地址:https://www.cnblogs.com/ahmasoi/p/3472111.html