题目链接：?problem=1349
Finally Aladdin reached home, with the great magical lamp. He was happier than ever. As he was a nice boy, he wanted to share the happiness with all people in the town. So, he wanted to invite all people in town in some place such that they can meet there easily. As Aladdin became really wealthy, so, number of people was not an issue. Here you are given a similar problem.
Assume that the town can be modeled as anm x n2D grid. People live in the cells. Aladdin wants to select a cell such that all people can gather here with optimaloverall cost. Here, cost for a person is the distance he has to travel to reach the selected cell. If a person lives in cell(x, y)and he wants to go to cell(p, q), then the cost is|x-p|+|y-q|. So, distance between(5, 2)and(1, 3)is|5-1|+|2-3|which is5. And theoverall costis thesummationof costs for all people.
So, you are given the information of the town and the people, your task to report a cell which should be selected by Aladdin as the gathering point and theoverall costshould be as low as possible.
Input
Input starts with an integerT (≤ 20), denoting the number of test cases.
Each case starts with a blank line. Next line contains three integers:m,nandq (1 ≤ m, n, q ≤ 50000),mandndenote the number of rows and columns of the grid respectively. Each of the nextqlines contains three integersu v w (1 ≤ u ≤ m, 1 ≤ v ≤ n, 1 ≤ w ≤ 10000), meaning that there arewpersons who live in cell(u, v). You can assume that there are no people in the cells which are not listed. You can also assume that each of theqlines contains a distinct cell.
Output
For each case, print the case number and the row and column position of the cell where the people should be invited. There can be multiple solutions, any valid one will do.
Sample InputOutput for Sample Input
2
5 1 1
2 1 10
5 5 4
1 1 1
2 2 1
4 4 1
5 5 1
Case 1: 2 1
Case 2: 3 3
Note
1.This is a special judge problem; wrong output format may cause ‘Wrong Answer’.
2.Dataset is huge, use faster I/O methods.
代码如下：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{int u, v;int w;} a[50047];bool cmp_u(node a, node b){return a.u < b.u;}bool cmp_v(node a, node b){return a.v < b.v;}int main(){int t;scanf("%d",&t);int m, n, q;int cas = 0;while(t–){scanf("%d%d%d",&m,&n,&q);int sum = 0;for(int i = 0; i < q; i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);sum += a[i].w;}sort(a,a+q,cmp_u);int tt;if(sum%2){tt = (sum+1)/2;}else{tt = sum/2;}int ansx = 0, ansy = 0;int tsum = 0;for(int i = 0; i < q; i++){tsum += a[i].w;if(tsum >= tt){ansx = a[i].u;break;}}tsum = 0;sort(a,a+q,cmp_v);for(int i = 0; i < q; i++){tsum += a[i].w;if(tsum >= tt){ansy = a[i].v;break;}}printf("Case %d: %d %d\n",++cas,ansx,ansy);}return 0;}
，走马观花之外，这才是深入体验，探索自我的最佳时间，
