题意简述
在二维平面上有 $n$ 个点 $(x_i, y_i)$ ，其中 $n$ 为偶数。选择 $\tfrac{n}{2}$ 个不相邻的点对 $(a_i, b_i)$ ，使点对之间的曼哈顿距离之和最大。换句话说，最大化
思路分析
多想一点。
$\max \sum(|x_i-x_j|+|y_i-y_j|)=\max\sum|x_i-x_j|+\max\sum|y_i-y_j|$。
所以应该取 $X$ 的最大的一半的点和 $X$ 最小的一半的点去配对。
以及取 $Y$ 最大的一半的点和 $Y$ 最小的一半的点去配对。
怎么配？
记 $X_l$ 表示 $X$ 坐标最小的一半的点，$X_r$ 表示 $X$ 坐标最大的一半的点，$X_l \cap X_r=\varnothing$
记 $Y_l$ 表示 $Y$ 坐标最小的一半的点，$Y_r$ 表示 $Y$ 坐标最大的一半的点，$Y_l \cap Y_r=\varnothing$
我们从 $X_l \cap Y_l$ 中取点与 $X_r \cap Y_r$ 中的点配对，从 $X_l \cap Y_r$ 中取点与 $X_r \cap Y_l$ 中的点配对。
这样我们可以保证，$(X_l \cap Y_l) \cap (X_r \cap Y_r) = \varnothing$，$(X_l \cap Y_r) \cap (X_r \cap Y_l) = \varnothing$。
也就是说不会取到重复点。（实际上这四个交集之间互相取交集得到的都是空集）
接下来是为什么可以成对取出？
记上述四个交集的大小分别为 $a,b,c,d$。
$a+c=b+d$，因为 $a+c$ 表示 $X_l \cap Y$ 的大小，$b+d$ 表示 $X_r \cap Y$ 的大小。$|X_l|=|X_r|$.
$a+d=b+c$，因为 $a+d$ 表示 $X \cap Y_l$ 的大小，$b+c$ 表示 $X\cap Y_r$ 的大小。$|Y_l|=|Y_r|$.
所以 $a=b$，$c=d$。即总能成对取出。