首先把切比雪夫距离转化为曼哈顿距离：$(x,y)\to(\dfrac{x+y}{2},\dfrac{x-y}{2})$。
之后枚举每个点 $j$ 作为终点，计算距离和。
把横坐标之差和纵坐标之差分开考虑：
横坐标之差：
先按 $x$ 排序，之后计算前缀和 $\textit{sum}$。

$$\begin{aligned} \textit{dis}&=\sum_{i=1}^n |x_i-x_j|\\ &=\sum_{i=1}^j(x_j-x_i)+\sum_{i=j+1}^n(x_i-x_j)\\ &=j\cdot x_j-\textit{sum}(i)+\textit{sum}(n)-\textit{sum}(i)-(n-j)\cdot x_j\\ &=(2j-n)x_j-2\cdot\textit{sum}(i)+\textit{sum}(n) \end{aligned}$$

纵坐标同理。
最后对每个点的答案取 $\min$ 即可。
注意开 long long。

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n;
struct node
{
    int x, y, id;
} d[N];
bool cmpx(node x, node y) { return x.x < y.x; }
bool cmpy(node x, node y) { return x.y < y.y; }
ll s[N], ans[N], fr = (1ll << 62);

int main()
{
    cin >> n;
    for (int i = 1, x, y; i <= n; i++)
    {
        cin >> x >> y;
        d[i].id = i;
        d[i].x = x + y, d[i].y = x - y;
    }
    sort(d + 1, d + n + 1, cmpx);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + d[i].x;
    for (int j = 1; j <= n; j++)
        ans[d[j].id] += 1ll * (2 * j - n) * d[j].x - s[j] * 2 + s[n];
    sort(d + 1, d + n + 1, cmpy);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + d[i].y;
    for (int j = 1; j <= n; j++)
        ans[d[j].id] += 1ll * (2 * j - n) * d[j].y - s[j] * 2 + s[n];
    for (int i = 1; i <= n; i++) fr = min(fr, ans[i]);
    cout << fr / 2;
    return 0;
}