### PROBLEM LINK

### DIFFICULTY

MEDIUM

### EXPLANATION

First try to solve the 1-D version. You have N integer points marked on a number line, the point(s) that minimze the sum of the distances from all the points lie between the median points. In case, N is even, there are two median points. For example,for N = 4, and points {2,3,5,6} , we can easily calculate that {3,4,5} are the integer points that will minimize the sum of distances from all the other points in {2,3,5,6}.

We can extend this to the 2-D version. First thing to realize is that we can treat X and the Y coordinates independently of each other. Let A be the answer to solve the 1-D version on X coordinates. Let B be the answer to solve the 1-D version on Y coordinates. The final answer is simple A*B.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.