title: Minimum Sum of All Travel Times
body: <p>I found a puzzle online on <a href="http://www.interviewstreet.com/recruit/challenges/dashboard/" rel="noreferrer">interviewStreet</a> and tried to solve it as follows:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I thought first about writing a solution in n² complexity in time, but the constraints are</p>
  
  <blockquote>
    <p>1&lt;=N&lt;=10^5 and The absolute value of each co-ordinate in the input will be atmost 10^9</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>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&lt;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&lt;length;i++){
          if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))&lt;tmp){
              tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
              tmpCur = i;
          }
      }
      for(i=0;i&lt;length;i++){
          if(i!=tmpCur)
              resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1]));
      }
  
      return resul;
  }
  </code></pre>
  
  <p>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</p>