Description: 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
- [travSrcCVar] - vehicle refueling will issue the restric
- [sanweipingbao] - using the Windows OpenGL 3D rendering pi
- [lotteryproblem] - lottery math lottery problem.pdf
- [POST] - The problem of location selection of pos
- [factor] - Description of laquo: The positive integ
- [permrank] - The algorithm realizes the dictionary or
- [Exam2] - MFC programming using the program to ach
- [pipe] - An oil company plans to construct a east
- [200710209193659] - A complete set of a company
- [pipe] - An oil company plans to construct a east
File list (Check if you may need any files):
Download