Coming Back 2

題目描述

在一個街區中，住着n個你的小夥伴，他們的位址用整點pi=(xi,yi)來表示（0<=xi<=100，0<=yi<=100，pi=pj iff i=j），其中每個小夥伴被賦予一個正整數權值Wi，以表示你們的友好程度。這時候問題又就來了，你要在這條街上尋找一個位置（這裡特别說明，該位置可以是街區中任意一個位置，不必是其中某個小夥伴的住處）居住一段時間，你希望這個位置能夠最大程度友善與各個小夥伴交流，同時又要考慮到與不同小夥伴的要好程度。

為了簡單起見，我們認為你的要求等價于到n個小夥伴那裡的距離與權值的乘積和最小（ie. argmin_{p} sigma Wi*|p-pi|,其中定義|.|為曼哈頓距離,即|(m,n)-(a,b)|=|m-a|+|n-b|,可以看出這個距離也與在街區中的需要走的路程相一緻）。

輸入

多組測試資料。

每組測試資料的第一行為正整數n，表示有n隻小夥伴；

接下來有n行，每行有3個正整數，分别表示第i個小夥伴的位址坐标xi，yi（0<=xi<=100，0<=yi<=100）和你們的友好程度Wi（Wi很小，你無須擔心，保證sigma Wi在int範圍内）。

輸出

對于每組資料，輸出一行，包含2個整數，即你標明的将要居住的位置坐标（x,y）（如果有多個選擇，則輸出最左上的位置）。

樣例輸入

3 

1 2 2

2 4 1

3 3 4

樣例輸出

3 3

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 150

struct point
{
    int x, y;
    int num;
};

bool cmpx(point a, point b)
{
    return a.x < b.x;
}

bool cmpy(point a, point b)
{
    return a.y < b.y;
}

point p[MAXN];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int number = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].num);
            number += p[i].num;
        }
        number = (number+1) / 2;
        sort(p, p+n, cmpx);
        int numx = number;
        int j = 0;
        while(numx > 0)
        {
            numx -= p[j].x;
            j++;
        }
        printf("%d", p[j-1].x);
        sort(p, p+n, cmpy);
        int numy = number;
        j = 0;
        while(numy > 0)
        {
            numy -= p[j].y;
            j++;
        }
        printf(" %d\n", p[j-1].y);
    }
}