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.
median has equal number of numbers on both of its side. so lets say x is your median point for n points. Moving it to left means subtracting n/2 from the sum at x. However you have made the point far from the right side n/2 points. So you add n/2 again. Plus it’s possible that now more points exist in the right side. For example rrrxrrr. moving x to left means rrrxrrrr. As you see, now you are adding more to the optimal sum and subtracting less. It is clear why x is the optimal place to choose now.
Proof for 1-D version.
Let us consider an arbitrary point X. Let there be L number of points to the left of point X and R number of points to the right of X. Now, if L > R, let us move our point X one step to the left at X-1. Our new sum of distances will be oldsum + R - L. Note that R-L is < 0 so the new sum of distances < oldsum. So as long as there are more points to the left of our current point than on the right, we can keep moving left and decrease our sum. The same logic can be applied when R > L. This will continue till R == L. The point where the number of points to the left is the same as the number of points to the right is called the median. Hence Proved.