输油管道问题
题目背景
听说最近石油危机。
所以想到了这题。
题目描述
某石油公司计划建造一条由东向西的主要输油管道。
该管道要穿过一个有 $n$ 口油井的油田。从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。
如果给定 $n$ 口油井的位置,及它们的 $x$ 坐标(东西向)和 $y$ 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可规定时间内确定主管道的最优位置。
输入输出格式
输入格式
第一行是油井数 $n$。
接下来 $n$ 行是油井的位置,每行 $2$ 个整数 $x$ 和 $y$。
输出格式
只有一行,表示油井到主管道之间的输油管道最小长度总和。
输入输出样例
输入样例 #1
5
1 2
2 2
1 3
3 -2
3 3
输出样例 #1
6
说明
### 数据范围及约定
对于全部数据,$1 \le n \le 10000$,$-10^4 \le x,y \le 10^4$。