Manhattan distance |x₁−x₂| + |y₁−y₂| is separable — the optimal x and y can be chosen independently. The problem reduces to finding the point that minimizes Σ|xi − x| plus Σ|yi − y|.

The median minimizes the sum of absolute deviations. Sort the x-coordinates, pick the median (middle element for odd n, any value between the two middle for even n), then do the same for y. Sum |xi − x_med| + |yi − y_med| for the answer.

For an even number of points, any point on the line segment between the two middle x (or y) values gives the same minimal sum, so picking either middle element is correct. Watch for integer overflow if coordinates are large — use 64-bit arithmetic.