我发现了一个谜在线上 interviewStreet 并试图解决它，如下所示：

I found a puzzle online on interviewStreet and tried to solve it as follows:

有一个无限整数格在了N人有自己的房子上。他们决定   团结在一个共同聚会的地方，这是别人的房子。从任何给定的小区，所有8   相邻单元可达1单位的时间。例如：（X，Y）能够从到达（X-1，Y + 1）   在时间的单个单元。找到其中最小的总和一个共同的聚会场所   所有的人的旅行时间。

There is an infinite integer grid at which N people 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+1) in a single unit of time. Find a common meeting place which minimizes the sum of the travel times of all the persons.

我想先说一下写N²复杂的解决方案的时候，但约束

I thought first about writing a solution in n² complexity in time, but the constraints are

1所述; = N＆其中; = 10 ^ 5和每个坐标输入​​的绝对值将atmost 10 ^ 9

1<=N<=10^5 and The absolute value of each co-ordinate in the input will be atmost 10^9

于是，我改变了我的第一个办法，而不是看的距离和旅行时间的问题，我看了看不同的房子为不同机构不同的权重。代替计算所有的距离和，我寻找该组体的重心。

So, I changed my first approach and instead of looking at the problem with the distances and travel times, I looked at the different houses as different bodies with different weights. And instead of calculating all the distances, I look for the center of gravity of the group of bodies.

下面是我的求解功能的$​​ C $ C，vectorToTreat是lengthX2表存储有关在网格点的所有数据，并resul是打印到标准输出数量：

Here's the code of my "solve" function, vectorToTreat is an lengthX2 table storing all the data about the points on the grid and resul is the number to print to stdout:

long long solve(long long** vectorToTreat, int length){
    long long resul = 0;
    int i;
    long long x=0;
    long long y=0;
    int tmpCur=-1;
    long long tmp=-1;
    for(i=0;i<length;i++){
        x+=vectorToTreat[i][0];
        y+=vectorToTreat[i][1];
    }
    x=x/length;
    y=y/length;
    tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y));
    tmpCur = 0;
    for(i=1;i<length;i++){
        if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){
            tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
            tmpCur = i;
        }
    }
    for(i=0;i<length;i++){
        if(i!=tmpCur)
            resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1]));
    }

    return resul;
}

现在的问题是，我通过12正式测试情况下超过13了，我看不出有什么我做错了，什么想法？ 提前致谢。 AE

The problem now is that I passed 12 official test cases over 13, and I don't see what I'm doing wrong, any ideas? Thanks in advance. AE

推荐答案

您好，感谢您的回答和评论，他们是非常有益的。 我终于放弃了对我的算法使用的重心，当我跑就可以了一些样品，我注意到，当房屋都聚集在不同的村庄，它们之间的距离不同，该算法是行不通的。 如果我们认为@Rostor上述的例子：

Hello and thanks to you for your answers and comments, they were very helpful. I finally gave up on my algorithm using the center of gravity, when I ran some samples on it, I noticed that when the houses are gathered in different villages with different distances between them, the algorithm does not work. If we consider the example that @Rostor stated above:

（0,0），（1,0），（2000,0），（3000,0），（3001,0），（3002，0），（3003，0）

(0,0), (1,0), (2000,0), (3000,0), (3001,0), (3002, 0), (3003, 0)

使用重心算法回答说，第三家是解决方案，但正确的答案是第四家。 权概念来在这类问题用的是中值，并使其适应尺寸通缉。 这里是一个伟大的文章在谈论的几何平均，希望有所帮助。

The algorithm using the center of gravity answers that the 3rd house is the solution, but the right answer is the 4th house. The right notion to use in this kind of problems is the median, and adapt it to the dimensions wanted. Here is a great article talking about The Geometric median, Hope it helps.