输油管道问题

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

给定n口油井的位置, 计算各油井到主管道之间的输油管道最小长度总和。

输入格式:

输入的第1 行是油井数n，1<=n<=10000。接下来n 行是

油井的位置，每行2个用空格割开的整数 x和 y，-10000<=x，y<=10000。

输出格式:

输出油井到主管道之间的输油管道最小长度总和。

输入样例:

1. 5
2. 1 2
3. 2 2
4. 1 3
5. 3 -2
6. 3 3

输出样例:

6

思路：首先我们从题目可以分析得出横坐标任意位置都有管道，所以我们只需要分析纵坐标就行了

情况1：两个油井，在两个纵坐标中间位置最佳

情况2：三个油井的情况y1、y2、y3，即到三点的距离最近

情况n：n个y坐标的中位数

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int x, b[N], sum;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> x >> b[i];
    sort(b, b + n);
    int mid = b[n / 2];
    for (int i = 0; i < n; i ++ )
        sum += abs(mid - b[i]);
    cout << sum;
    return 0;
}