Franklin's Trouble

Description

Professor Franklin is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of M wells. From each well, a sub-pipeline is to be connected directly to the main pipeline along a shortest path (either north or south). Given x- and y-coordinates of the wells, the professor wants to pick the optimal location of the main pipeline, which means to minimize the total length of the sub-pipelines. Franklin is not good at calculation, but you are. Can you help him?

Input

The first line of input contains a single integer N representing the number of oil fields. Then N field descriptions follow. Each field description starts with an integer M representing the number of wells in this field. Each well is represented by a point (x, y) (both x and y are integers). You can assume all integers are between 1 and 100 and no two wells share the same x-coordinate.

Output

For each field, output the total length of the sub-pipelines. The length should be minimized.

Sample Input

1

2

1 0

2 1

 

Sample Output

1

 

Explanation

In sample input, there is only one case. In this case, the main pipeline can be located at any position between y=0 and y=1 lines to reach the optimal result 1.

 

 

 

题目意思就是M个点，求一条水平线，使得所有点到水平线的距离之和最小。输出最小距离之和

输入数据的X坐标不相等。

 

很简单的数学题，明显应该选在Y坐标的中位数处，可以使得距离之和最小；；

 

#include
      
       #include
       
        using namespace std;const int MAXN=1000;int y[MAXN];int main(){    int T;    int n;    int x;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        for(int i=0;i