Introduction - If you have any usage issues, please Google them yourself
The problem of pipeline problem of 2-1 oil pipeline is realized
Description of laquo:
An oil company plans to build a main pipeline from east to west. The pipe runs through an oil that has n Wells
Field. Each well must have a pipeline connecting the shortest route (or south or north) to the main pipe. So if I have n oil
The position of the well, namely their x coordinates (east and west) and y coordinates (north-south direction), how to determine the optimal location of the main pipeline,
Even though the length of the pipeline between the oil Wells and the main pipeline is the smallest? It is proved that the main pipeline can be determined in linear time
The optimal position.
« programming tasks:
Given the location of the n mouth well, the total length of the pipeline between the oil Wells and the main pipelines is calculated.
« data input:
Input data is provided by input.txt. The first line of the document is the well number n, 1£ n£ 10000. The next n rows are
The location of the well, two integers x and y, -10000£ x, y£ 10000.
« result output:
At the end of the program run, the result is output to the file output.txt. The number in line 1 of the file is the well
The minimum length of the pipeline between the main pipelines.
An example of the input file example output file
Input. TXT output. TXT
5
1 2
2 2
1 3
3-2
3 3
6