洛谷P3964 [TJOI2013]松鼠聚会

这个小辣鸡怎么连切比雪夫距离都不会啊。。。

题目

https://www.luogu.com.cn/problem/P3964

思路

切比雪夫距离

定义

点\((x1,y1)\)到\((x2,y2)\)的切比雪夫距离为： \(dis=max(\lvert x1-x2\rvert,\lvert y1-y2\rvert)\)

切比雪夫距离与曼哈顿距离的变换

显然这个东西既包含绝对值又包含最值，非常不好处理。

但是我们有一种转化方法珂以将切比雪夫距离转化成曼哈顿距离。当然逆变换也必然是存在的。我这里推一遍曼哈顿距离到切比雪夫距离的变换。

假设两个点为\((x1,y1)\)，\((x2,y2)\)，那么它们的曼哈顿距离为：\(\lvert x1-x2\rvert + \lvert y1-y2\rvert\)，考虑把绝对值拆掉：

\(\lvert x1-x2\rvert + \lvert y1-y2\rvert\)=\(max(x1-x2+y1-y2 , x1-x2+y2-y1 , x2-x1+y1-y2 , x2-x1+y2-y1)\)

现在发现式子已经变成了一个max的形式。注意到\(x1-x2+y1-y2=-(x2-x1+y2-y1)\)，把式子中互为相反数的部分并在一起，得：

\(max(max(x1-x2+y1-y2,x2-x1+y2-y1),max(x1-x2+y2-y1,x2-x1+y1-y2))\)

就是\(max(\lvert x1-x2+y1-y2\rvert,\lvert x1-x2-(y1-y2)\rvert)\)

=\(max(\lvert x1+y1-(x2+y2)\rvert,\lvert x1-y1-(x2-y2)\rvert)\)

对照切比雪夫距离的定义，我们令 \(x1'=x1+y1\) , \(y1'=x1-y1\) , \(x2'=x2+y2\) , \(y2'=x2-y2\)

则距离可写为 \(max(\vert x1'-x2'\rvert,\lvert y1'-y2'\rvert)\)

所以曼哈顿意义下的\((x,y)\)，对应于切比雪夫意义下的\((x+y,x-y)\)

同样，我们珂以很容易地做一个逆变换，把切比雪夫意义下的\((x,y)\)映射到曼哈顿意义下的\((\frac{x+y}{2},\frac{x-y}{2})\)。

（这堆式子用了markdown还是好丑啊，其实自己在草稿上推一遍挺快的qwq）

解题

现在问题变成了，给出一堆点，求其中的一个点，使所有点到该点的曼哈顿距离之和最小。

枚举每一个点，计算集合点在该点的代价。那就是很经典的珂以用前缀和维护的问题了。

代码

#include
#include
#include
#define ll long long
#define maxn (int)(1e5+10)
using namespace std;
struct point{
    ll x,y;
} p[maxn];
bool cmp1(point p1,point p2){
    return p1.x