打水井

打水井
陶渊明来到了桃花源,这里的民风淳朴,但是陶渊明马上发现了不足,这里没有水
井!!!善良的陶渊明想要在这里打出一口水井。
在桃花源,人们居住的位置只能是坐标的整数点,一个坐标可以即有人,又有水井。同时,这里的道路是横平竖直的。比如,(1,2)点到(3,1)点的距离为3。
现在给你桃花源里面所有人的坐标,你能求出水井应该打在什么坐标上,使得人们到水井的总距离最短?

输入格式:
第一行一个整数T(1 <= T <= 20),代表测试组数。
对于每组测试数据,第一行一个整数n(1 <= n <= 20),代表有n个人。接下来n行,每行两个数x,y(1<= x,y <= 100)代表(x, y)处有一个人。

输出格式:
对于每个测试数据,输出一个整数,代表人们距离水井的最短距离和。

样例输入:

2

3

1 1

2 1

1 2
5
2 9

5 20

11 9

1 1

1 20

样例输出:

2
44

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int T,n,a[20][20],sum1[20];
    cin>>T;//测试组数

for(int j=0;j<T;j++)//控制测试的组数
   {
    ci啊、n>>n;//村里的人数
    for (int i=0;i<n;i++)
        for(int j=0;j<=1;j++)
            cin>>a[i][j];
    int sum=4000,sum0=0;//距离水井的距离的和
    for(int x=0;x<100;x++)//设置水井的位置
      {
        for(int y=0;y<100;y++)
           {
               for (int i=0;i<n;i++)
              {
                  sum0+=abs(a[i][0]-x)+abs(a[i][1]-y);

              }
              if(sum>=sum0)
                sum=sum0;
              sum0=0;//恢复到另

           }
      }
     sum1[j]=sum;//储存每一组的数据
   }
   for(int j=0;j<T;j++)
        cout<<sum1[j]<<endl;
    return 0;
}

 

上一篇:1.从左往右尝试模型(背包问题)


下一篇:地铁计费