某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，使各油井到主管道之间的输油管道长度总和最小的位置?可在线性时间内确定主管道的最优位置。给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。输入格式：输入的第1行是油井数n，1<=n<=10000。接下来n行是油井的位置，每行2个用空格割开的整数x和y，-10000<=x，y<=10000。输出格式：输出油井到主管道之间的输油管道最小长度总和。输入样例：51 22 21 33 -23 3输出样例：6

这是一个经典的最小二乘问题，可以使用线性回归求解。具体来说，我们可以将问题转化为求解一条直线，使得所有点到该直线的距离平方和最小。

假设直线的方程为 $y=ax+b$，则点 $(x_i,y_i)$ 到该直线的距离为：

$$d_i=\frac{|ax_i-y_i+b|}{\sqrt{a^2+1}}$$

因此，所有点到该直线的距离平方和为：

$$S=\sum_{i=1}^nd_i^2=\sum_{i=1}^n\frac{(ax_i-y_i+b)^2}{a^2+1}$$

我们要求的是 $S$ 的最小值，可以对 $a$ 和 $b$ 分别求偏导数，得到：

$$\frac{\partial S}{\partial a}=2\sum_{i=1}^n\frac{(ax_i-y_i+b)x_i}{(a^2+1)^2}=0$$

$$\frac{\partial S}{\partial b}=2\sum_{i=1}^n\frac{(ax_i-y_i+b)}{(a^2+1)^2}=0$$

由于 $\frac{\partial S}{\partial a}$ 和 $\frac{\partial S}{\partial b}$ 都是关于 $a$ 和 $b$ 的二次函数，因此可以通过求解方程组得到最优解。

具体来说，可以将方程组变形为：

$$\begin{cases}\sum_{i=1}^nx_i^2a+\sum_{i=1}^nx_ib=\sum_{i=1}^nx_iy_i\\\sum_{i=1}^nx_ia+\sum_{i=1}^nb=\sum_{i=1}^ny_i\end{cases}$$

然后使用高斯消元法求解即可。时间复杂度为 $O(n)$。

代码如下：