## Editorial for UHCC1 P4 - Manhattan Distance

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RAINY

Let's consider an easier version of the problem, suppose you only need to find one point that has the minimum Manhattan distance to all points.

Let this point be , then the distance to all points can be written as this: . As the and coordinate are independent, we minimize each summand seperately.

Finding the the value of that minimizes is a classic problem, which you can solve by calculating the median of the array . In fact, moving away from will never decrease the total sum.

Now back to the original problem, we need to find two points that minimize the distances. It's clear that the point we found above must be one of them. In fact the second point is just near the first point. Let the second point be , then I claim , that is, it's one of the four neighbours of the first point.

Still, we consider each dimension seperately, find that minimize . Suppose is the median, as moving away from it will always increase the answer, therefore, the optimal choice of would be one of . Therefore in the two dimensional case, we must have .

You could check all integer points around , but it suffices to check only the four neighbours.