PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
We can solve this problem by using Ternary Search algorithm:

At first, we take a look at a subproblem: Finding an integer point on the line y=c satisfying its sum of distances to N given points (S’) is mininum. In this subproblem, every integer point on the line y=c will lead to a respective value of S’, and all of that values together make a paraboliclike curve on the plane. So we can use Ternary Search algorithm to find the respective mininum value of S’.

Just imagine that the problem we have to solve is upgraded from the above one, since all the minimum values of S’ will together make a paraboliclike curve from which we can find the minimum value of S. Our task is applying Ternary Search algorithm again!

On the other hand, we can also imagine that all values of S (for respective integer points) will together make a parabola in 3Dspace, so our work is using Ternary Search in certain layers when we try to cut it by a plane!
See the source code for details and find more information about the Ternary Search algorithm at: http://en.wikipedia.org/wiki/Ternary_search
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.