打水井
陶渊明来到了桃花源,这里的民风淳朴,但是陶渊明马上发现了不足,这里没有水
井!!!善良的陶渊明想要在这里打出一口水井。
在桃花源,人们居住的位置只能是坐标的整数点,一个坐标可以即有人,又有水井。同时,这里的道路是横平竖直的。比如,(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; }