经典结论题。但是我不会
题意：给出 \(n\) 个点 \((x_i,y_i)\)，求出 \(\min_{i=1}^n \sum_{j=1}^n \max(|x_i-x_j|,|y_i-y_j|)\)。
\(\max(|x_i-x_j|,|y_i-y_j|)\) 为两点间的切比雪夫距离，\(|x_i-x_j|+|y_i-y_j|\) 两点间曼哈顿的距离。
切比雪夫距离太难算了，考虑转成曼哈顿距离。
\[|x_1-x_2|+|y_1-y_2| \\
=\max(x_1-x_2+y_1-y_2,x_2-x_1+y_1-y_2,x_1-x_2+y_2-y_1,x_2-x_1+y_2-y_1) \\
=\max(x_1+y_1-x_2-y_2,-x_1+y_1+x_2-y_2,x_1-y_1-x_2+y_2,-x_1-y_1+x_2+y_2) \\
=\max(x_1+y_1-x_2-y_2,-x_1-y_1+x_2+y_2,-x_1+y_1+x_2-y_2,x_1-y_1-x_2+y_2) \\
\]
注意到前两项、后两项互为相反数，于是有：
\[|x_1-x_2|+|y_1-y_2| \\
=\max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|)
\]
这里分别取了首项和末项，发现 \((x_1,y_1),(x_2,y_2)\) 的曼哈顿变成了 \((x_1+y_1,x_1-y_1),(x_2+y_2,x_1-y_1)\) 的切比雪夫距离距离，那么把每一个 \((x_i,y_i)\) 变为 \((x_i+y_i,x_i-y_i)\) 后，原来两点间的曼哈顿距离变为现在的切比雪夫距离。
将切比雪夫距离变为曼哈顿距离，如果 \((x_1,y_1)\) 变为 \((x_2,y_2)\)，那么：
\[\left\{\begin{matrix}
x_1=x_2+y_2 \\
y_1=x_2-y_2
\end{matrix}\right.
\]
解得
\[\left\{\begin{matrix}
x_2=\frac{x_1+y_1}{2} \\
y_2=\frac{x_1-y_1}{2}
\end{matrix}\right.
\]
所以把每一个 \((x_i,y_i)\) 变为 \((\frac{x_i+y_i}{2},\frac{x_i-y_i}{2})\) 后，原来两点间的切比雪夫距离变为现在的曼哈顿距离。
转化后，问题变为 \(\min_{i=1}^n \sum_{j=1}^n |x_i-x_j|+|y_i-y_j|\)。
此时横坐标和纵坐标独立求解即可，时间复杂度 \(O(n log n)\)。