Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).

UPD: I understood the problem incorrectly. Please check the later comments in this thread.

For each point $$$i$$$, let $$$a_i = x_i + y_i$$$ and $$$b_i = x_i - y_i$$$.

Let $$$d(i, j) = max(|x_i - x_j|, |y_i - y_j|)$$$.

Without loss of generality, assume $$$x_i \ge x_j$$$. Now $$$|x_i - x_j| = x_i - x_j$$$. And

$$$d(i, j) = max(|x_i - x_j|, |y_i - y_j|)$$$

$$$d(i, j) = max(x_i - x_j, |y_i - y_j|)$$$.

$$$\displaystyle d(i, j) = \frac{x_i - x_j + |y_i - y_j| + |x_i - x_j - |y_i - y_j||}{2}$$$ (According to this)

$$$2\cdot d(i, j) = x_i - x_j + |y_i - y_j| + |x_i - x_j - |y_i - y_j||$$$

Case 1: $$$y_i \ge y_j$$$

$$$2\cdot d(i, j) = x_i - x_j + y_i - y_j + |x_i - x_j - y_i + y_j|$$$

$$$2\cdot d(i, j) = x_i + y_i - x_j - y_j + |x_i - y_i - x_j + y_j|$$$

$$$2\cdot d(i, j) = a_i - a_j + |b_i - b_j|$$$

Because $$$x_i \ge x_j$$$ and $$$y_i \ge y_j$$$ are assumed,

$$$a_i \ge a_j$$$ must be true.

$$$2\cdot d(i, j) = |a_i - a_j| + |b_i - b_j|$$$

$$$\displaystyle d(i, j) = \frac{|a_i - a_j| + |b_i - b_j|}{2}$$$

Case 2: $$$y_i < y_j$$$

$$$2\cdot d(i, j) = x_i - x_j + (- y_i + y_j) + |x_i - x_j - (- y_i + y_j)|$$$

$$$2\cdot d(i, j) = x_i - x_j - y_i + y_j + |x_i - x_j + y_i - y_j|$$$

$$$2\cdot d(i, j) = x_i - y_i - x_j + y_j + |x_i + y_i - x_j - y_j|$$$

$$$2\cdot d(i, j) = b_i - b_j + |a_i - a_j|$$$

Because $$$x_i \ge x_j$$$ and $$$y_i < y_j \Leftrightarrow -y_i > y_j$$$ are assumed,

$$$x_i - y_i > x_j - y_j$$$

$$$b_i > b_j$$$ must be true.

$$$2\cdot d(i, j) = |b_i - b_j| + |a_i - a_j|$$$

$$$\displaystyle d(i, j) = \frac{|b_i - b_j| + |a_i - a_j|}{2}$$$

We can see that in both cases, $$$\displaystyle d(i, j) = \frac{|a_i - a_j| + |b_i - b_j|}{2}$$$.

This is equal to the manhattan distance of points $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$ divided by two. For implementation, we can actually forget about the "divided by two" part, since that just scales everything by a constant and doesn't affect which distances are larger than others.

Now the problem is to find the minimum sum of manhattan distances for each point. Manhattan distances for each coordinate are independent of each other and thus they can be calculated independently.

Let's consider some fixed point $$$i$$$ and the sum of distance differences of the $$$a$$$-coordinates:

$$$\displaystyle\sum_{j = 1}^n |a_i - a_j|$$$

$$$ = \displaystyle\sum_{a_j \le a_j} (a_i - a_j) + \displaystyle\sum_{a_j > a_j} (a_j - a_i)$$$

$$$ = \displaystyle\sum_{a_j \le a_j} a_i - \displaystyle\sum_{a_j \le a_j} a_j + \displaystyle\sum_{a_j > a_j} a_j - \displaystyle\sum_{a_j > a_j} a_i$$$

$$$ = [\text{count of } j \text{: } a_j \le a_i] \cdot a_i - \displaystyle\sum_{a_j \le a_j} a_j + \displaystyle\sum_{a_j > a_j} a_j - [\text{count of } j \text{: } a_j > a_i] \cdot a_i$$$

$$$ = \displaystyle\sum_{a_j > a_j} a_j - \displaystyle\sum_{a_j \le a_j} a_j + [\text{count of } j \text{: } a_j \le a_i] \cdot a_i - [\text{count of } j \text{: } a_j > a_i] \cdot a_i$$$

The first and second terms are just prefix/suffix sums on the sorted array of all $$$a$$$-coordinates which can either be precalculated or calculated during iteration of the array. The last two terms can be calculated in $$$O(1)$$$ based the position of point $$$i$$$ in the sorted array of all $$$a$$$-coordinates. Thus, these values can be calculated for all points $$$i$$$ in $$$O(n \log n)$$$ (due to sorting the points). Now, we can do the same for all $$$b$$$-coordinates and calculate the sum of differences of those. The total manhattan distance, which is equal to twice the original distance, is now the sum of these two sums of differences. Now we can find the minimum total distance in $$$O(n)$$$.