题目: http://acm.hdu.edu.cn/showproblem.php?pid=4312
Meeting point-2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1231 Accepted Submission(s): 691
It's an opportunity to show yourself in front of your predecessors!
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1), (x-1,y+1), (x-1,y-1), (x+1,y+1), (x+1,y-1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2
15
14
38
In the first case, the meeting point is (0,2); the second is (0,0), the third is (1,-1) and the last is (-1,-1)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MAXN 100010
#define INF 1000000000000000LL
#define ULL unsigned long long
struct node
{
LL a1,b1;
}x[MAXN],y[MAXN];
ULL qzx[MAXN],qzy[MAXN],q1[MAXN],q2[MAXN],ans[MAXN];
LL read()
{
LL s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
bool cmp(node aa,node bb)
{
return aa.a1<bb.a1;
}
int main()
{
LL n,i,x1,y1,x2,y2,dis,T;
ULL sum,sum1,MN;
T=read();
while(T--)
{
n=read();
for(i=;i<=n;i++){x[i].a1=read();y[i].a1=read();x1=(x[i].a1+y[i].a1);y1=(x[i].a1-y[i].a1);x[i].a1=x1;y[i].a1=y1;x[i].b1=y[i].b1=i;}
sort(x+,x+n+,cmp);
sort(y+,y+n+,cmp);
qzx[]=qzy[]=q1[]=q2[]=;
for(i=;i<=n;i++)qzx[i]=qzx[i-]+(x[i].a1-x[i-].a1);
for(i=;i<=n;i++)q1[i]=q1[i-]+qzx[i];
for(i=;i<=n;i++)qzy[i]=qzy[i-]+(y[i].a1-y[i-].a1);
for(i=;i<=n;i++)q2[i]=q2[i-]+qzy[i];
MN=INF;
memset(ans,,sizeof(ans));
for(i=;i<=n;i++)
{
sum=;
sum+=(qzx[i]*(i-)-q1[i-]);
sum+=(q1[n]-q1[i]-(n-i)*qzx[i]);
sum1=;
sum1+=(qzy[i]*(i-)-q2[i-]);
sum1+=(q2[n]-q2[i]-(n-i)*qzy[i]);
ans[x[i].b1]+=sum;
ans[y[i].b1]+=sum1;
}
for(i=;i<=n;i++)MN=min(MN,ans[i]);
printf("%lld\n",MN/2LL);
}
return ;
}