To find the number of points on a 2D grid? Given N points on a 2D grid of the form (X,Y) we need to find to find all the points (R,S) such that the sum of the distances between the point (R,S) and each of the N points given is as small as possible.
Distance measurement b/w 2 points is done as follows
distance between the points (A,B) and (C,D) = |A-C| + |B-D|.
Also :
1) In the N given points some points can be repeated
2) (R,S) can also be any of the N given points
3) All points must have integer co-ordinates.
Constraints:
$N \le 1000$,
$-10^8 \le X \le10^8$,
$-10^8 \le Y \le10^8$
One Such Input is as follows
N = 5
The 5 points are as follows
$(0, 0),
(-1, 0),
(1, 0),
(0, 1),
(0, -1)$
The number of points (R,S) is 1.
I have written a code for this but for large inputs it times out. I can paste the code here for reference. What i did was to form a polygon that surrounds all of these N points given and within this polygon calculate all the other points for smallest possible distance. But this technique won't work as values of X and Y are huge. Can You suggest me any formula of some sort or any observation so that it becomes easier for me to evaluate this function.
Thanks in advance
 A: For the corresponding problem in one dimension, the solution is to put $R$ at the median of the given numbers; if there are an even number of numbers, then the number of solutions is the number of (integer) medians, which is just the number of integers between the two points on either side of the median, inclusive. 
I suspect it's the same in two dimensions: take $R$ to be a median of the $x$-co-ordinates of the given points, and $S$ a median of the $y$-coordinates.  
EDIT: more detail, in response to comments. 
If you have an odd number of real numbers, $a_1\le a_2\le\cdots\le a_{2n-1}$, then the median is $a_n$. 
If you have an even number of real numbers, $a_1\le a_2\le\cdots\le a_{2n}$, then any number $x$ with $a_n\le x\le a_{n+1}$ will serve as a median. 
You take your given $N$ points, and you list all the $x$-coordinates; you take $R$ to be any median of these numbers. You list all the $y$-coordinates, and take $S$ to be any median of these numbers. 
Now look at the 4-point example in my comment. Since in your problem we are restricted to integer values, $R$, the median of $0,1,4,6$, can be any of the choices $1,2,3,4$; $S$, the median of $0,1,3,5$, can be any of the choices $1,2,3$; all told, then, there are $4\times3=12$ points $(R,S)$ that will do. 
I hope that makes the method clear. 
