CareerCup

may be it is fermat point of a traingle...

Euclidean distance or Manhattan distance?

That I am not sure!! :) Even dont know the difference

Cool!! Good to learn new thing. This was the only question given. I was thinking to solve it by taking meddle in 2D Matrix. and then find. Since from middle element, it could be the shortest path if 3 People are scattered very widely.
I think here we will go for Manhattan distance.

wen we hav to minimize distances for each .. shdnt we look for circumcenter of the triangle ? i cud b terribly wrong also :)

Gut feeling is that this is a version of TSP and thus NP-complete. I'd try simulated annealing, since there is an easy cost metric that can be incrementally refined in constant time at each iteration.

@Andy2000, after some mathematical calculations, i concluded that the distance will be minimum if we fix the meeting point as one of the person's co-ordinates. Can the meeting point be one of the person's position? If yes, the solution goes simple. O( N^2).
Let me know if i am missing anything.

Surely the answer is the centroid or "average" of the positions of the N people.

Let the position of person i be x_i, and a hypothesized meeting point be m. Then we want to find the m which minimizes the following
J(m) = \sum_{i=1}^N ||x_i - m||^2.

The easiest way to minimize this is take its derivative and set to zero. This gives us:
\nabla_m(J(m)) = \sum_{i=1}^N 2(x_i - m)
which equals
-2Nm + 2\sum_{i=1}^N x_i

Now setting this derivative to zero we see that
m = 1/N \sum_{i=1}^N x_i
which is the centroid of the people's locations.

I hope you don't mind the pseudo-latex code :-)

You want to compute the geometric median, which has no simple closed form expression but can be numerically approximated by convex optimization procedures. See the Wikipedia article 'geometric median' (whose link this site won't let me post) for a discussion and pointers to algorithms.

I think I can propose something and for N > 3, it can be generalized.

// y = mx+c notation
Struct line_t
{
    int x;
    int y;
    int slope;
};

We have to create 3 lines which pass through each of the three given positions and are perpendicular to the other two.

like, Line 1: passes through A, and is perpendicular to BC.
        Line 2: passes through B, and is perpendicular to AC.
and line 3 similarly.

these lines can be got by just finding the line y = mx+c, where m is the perpendicular slope of the other two lines. ( if m1 is the slope of BC, then the line through A should have slope -1/(m1).)

After your get two lines find thier intersection.

Now we gotta retrieve these two lines in our structs.

have a function similar to this.

void (int &x, int &y, struct line *line1, struct line *line2)
{
      // just do the mathematical equivalent of finding the intersection of two lines..
      multiply(line1, line2->y);
      multiply(line2, line1->y);
      // Im equating the mx + c with each of the y cordinate.
      // now two lines will have equal y cordinate.
      // *x = solve (line1, line2); // simply equate mx+c term and retrieve x;
      // now use *x, line to get y.
      // x , y is the required solution
}

Now every N greater than 3, break it down into triangles, find the point and again find the nearest of the respective points which are obtained. (corner case: if you get two points, find its midpoint and return it) eg: 6 people, 2 triangles, 2 points ==> mid point of these gives the reqd solution.


this is just on top of my mind, and would appreciate if someone has any thoughts to improve this.

Step 1 : Find the convex hull for the N points.
Step 2 : draw medians from each edge on the hull.
The meeting point would be the minimum distance between all points ?

I think it can be easily solved using below trick. for a given set of points say.. (x1,y1), (x2,y2), (x3,y3).... we need to find (mx,my) such that manhattan distance from all points to this is minimized. so we need to minimize,
|x1-mx| + |y1-my| +....
Note : here we are adding only positive numbers so if this is minimum then sum of square is also minimum..
(x1-mx)^2 + (y1-my)^2 + .....
expanding and solving we get...
(x1)^2 + (x2)^2 + ...
(y1)^2 + (y2)^2 + ...
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2

so in short we need to minimize the below term..
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2

which indirectly means first minimize it for x and then for y...

Just a thought: Could this be done using BFS, where each node in the graph would look like:

struct node{
  int Person1X,Person1Y,Person2X,Person2Y,Person3X,Person3Y;
  int steps;
}

While doing the BFS we could put a constraint, 
if steps>min(sum of any two edges of the triangle with 3 persons as vertices) return;

centroid will work. For 3 points it is X = (x1+x2+x3) /3 and Y = (y1 + y2 + y3)/3 and for n points it is (x1 + x2 +...xn)/n and (y1 + y2 + .. yn)/n

geometric median , (4 3 points knows as fermat point )

I hate when people simply write code and solve the same, without explanation. This reduces the quality of intelligence.

Writing code should be agnostic to language. The logic should be sound and stable.

Why not do the following (I'm generalizing for N persons):

For each person, find the Xmin, Ymin, Xmax and Ymax. This will form a bounding rectangle. Pick a point inside the rectangle. Cost so far is O(N) in time.

Once at that point, measure distances (L1 or L2 distances) to each person and sum. This is still O(N). Then I would try some gradient descent method as I would "walk" to neighbors to find a minimum.

Question: I can do this all in O(N) time with no significant extra memory... can I prove that the minimum I find is a global minimum and not a local minimum? I did see someone suggesting simulated annealing... similar idea and that might help avoid local minima if that's a problem. Still O(N).