题目链接：https://vjudge.net/contest/28079#problem/N
题目大意：给一个mxn的平面，有q个位置，每个位置坐标为（u,v）有w人，求一个点在平面内使得所有人都到这个点的曼哈顿距离之和最小（如 (x, y) 到 (p, q),那曼哈顿距离就是|x-p|+|y-q|）。
解题思路：分别按横纵坐标排序找出中位数即可（中位数请自行百度）。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e5+; struct node{
int x,y,cnt;
}a[N]; bool cmp1(node a,node b){
return a.x<b.x;
} bool cmp2(node a,node b){
return a.y<b.y;
} int main(){
int T;
scanf("%d",&T);
int cas=;
while(T--){
int m,n,q,x,y;
scanf("%d%d%d",&m,&n,&q);
int xsum=,ysum=,count=;
for(int i=;i<=q;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cnt);
count+=a[i].cnt;
}
int mid=(count+)/;
//按横坐标排序
sort(a+,a+q+,cmp1);
int sum=;
for(int i=;i<=q;i++){
sum+=a[i].cnt;
if(sum>=mid){
if(count&)
x=a[i].x;
else{
if(sum==mid)
x=(a[i].x+a[i+].x)/;
else
x=a[i].x;
}
break;
}
}
//按纵坐标排序
sort(a+,a+q+,cmp2);
sum=;
for(int i=;i<=q;i++){
sum+=a[i].cnt;
if(sum>=mid){
if(count&)
y=a[i].y;
else{
if(sum==mid)
y=(a[i].y+a[i+].y)/;
else
y=a[i].y;
} break;
}
}
printf("Case %d: %d %d\n",++cas,x,y);
}
}