Description

【Problem Description】

A petroleum company plans to build a main oil pipeline running east to west. The pipeline needs to pass through an oil field with n oil wells. Each oil well must have a branch pipeline connected to the main pipeline along the shortest path (either north or south). Given the positions of the n oil wells, i.e., their x-coordinates (east-west direction) and y-coordinates (north-south direction), how should the optimal position of the main pipeline be determined to minimize the total length of the branch pipelines connecting the wells to the main pipeline? Prove that the optimal position of the main pipeline can be determined in linear time.

【Programming Task】

Given the positions of n oil wells, write a program to calculate the minimum total length of the branch pipelines connecting the wells to the main pipeline.

Input Format

The first line of input is the number of oil wells n, where 1≤n≤10000. The next n lines specify the positions of the oil wells, each containing 2 integers x and y, where -10000≤x,y≤10000.

Output Format

At the end of the program execution, output the calculation result.

The first line of the output contains the minimum total length of the branch pipelines connecting the wells to the main pipeline.

```input1 5 1 2 2 2 1 3 3 -2 3 3 ``` ```output1 6 ``` ## 译文

CodesOnline