P1862 Oil Pipeline Problem

I heard there is an oil crisis recently. So I thought of this problem.

An oil company plans to build a main pipeline running from east to west. The pipeline must pass through an oil field that has $n$ wells. From each well, a feeder pipeline must connect to the main pipeline along the shortest path (either north or south). Given the positions of the $n$ wells, with their $x$ coordinates (east–west) and $y$ coordinates (north–south), determine the optimal position of the main pipeline so that the total length of the feeder pipelines from the wells to the main pipeline is minimized. Prove that the optimal position of the main pipeline can be determined within the time limit.

The first line contains the number of wells $n$. Each of the next $n$ lines contains the position of a well: two integers $x$ and $y$.

Output a single line with the minimum total length of the feeder pipelines from the wells to the main pipeline.

Constraints For all testdata, $1 \le n \le 10000$, $-10^4 \le x, y \le 10^4$. Translated by ChatGPT 5