Tricky Median Question Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.

Distance is measured in the following manner.

For a point (x,y) all 8 adjacent points have distance 1.

(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)


EDIT

More clearer explanation.

A function foo is defined as  

foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))


Find a point x such that sum([foo(x,y) for y in list_of_points]) is minimum.

Example

Input:

0 1
2 5
3 1
4 0


Output

3 1


Eg:
Distance between (4,5) and 6,7) is 2.

This can be done in O(n^2) time, by checking the sum of each pair.
Is there any better algorithm to do it?
I can imagine a scheme better than O(n^2), at least in the common case.

Build a quadtree out of your input points.  For each node in the tree, compute the number and average position of the points within that node.  Then for each point, you can use the quadtree to compute its distance to all other points in less than O(n) time.  If you're computing the distance from a point p to a distant quadtree node v, and v doesn't overlap the 45 degree diagonals from p, then the total distance from p to all the points in v is easy to compute (for v which are more horizontally than vertically separated from p, it is just v.num_points * |p.x - v.average.x|, and similarly using y coordinates if v is predominately vertically seperated).  If v overlaps one of the 45 degree diagonals, recurse on its components.

That should beat O(n^2), at least when you can find a balanced quadtree to represent your points.