1
$\begingroup$

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

1 Answers 1