「HCOI-R2」哀之距 官方题解
Wf_yjqd
·
·
题解
官方题解。
负责人只出了签到题我很愧疚。
\text{Subtask 0}
真的有人写吗。。根据题意直接 \operatorname{O}(n^6) 模拟。
注：文中复杂度中的 n 仅表示题面中 n,x,y 的数量级。
\text{Subtask 1}
对于任意两个矩形根据位置关系进行分讨得到题目中定义的矩形的距离，然后枚举取最大值。
具体见下方代码。
复杂度为 \operatorname{O}(n^2)。
\text{Subtask 2}
退化到点。
出题人一开始想到的问题其实是线段，后来发现改成矩形也无差。
这里懒得回想于是干脆直接给了点的部分分。
考虑两点之间距离就是直接切比雪夫距离，而其外层是一个 \max 取最大值。
恰好题目要求的是所有距离中的最大值，所以可以直接省去内层的（因为较小的一定不会影响最后的最大值）。
于是答案为 x 的极差与 y 的极差中的较大值。（其实与正解十分相似，我很担心有人写这个部分分结果不小心过了。。）
\text{Subtask 3}
考虑对于任意两个矩形与 \text{Subtask 2} 同理只需去掉绝对值，将 x,y 轴的答案拆开并不会影响正确性。（这样两方向上的答案不满足任取一点的切比雪夫距离的最小值的一定会得到负值，于是不影响答案）
没有理解请自行认真思考。
于是答案为 \max(\max\limits_{i=1}^n x_{i,0}-\min\limits_{j=1}^n x_{j,1},\max\limits_{k=1}^n y_{k,0}-\min\limits_{l=1}^n y_{l,1})。
复杂度 \operatorname{O}(n)，并没有卡排序的 \operatorname{O}(n\log n)
放一下代码吧。
验题人鸽了。
$100pts$：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll x,y,xx,yy,s,xxx,z,yyy;
int main(){
scanf("%d",&n);
xxx=z=0x3f3f3f3f3f3f3f3f;
while(n--){
scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
s=max(s,y);
xxx=min(xxx,yy);
z=min(z,xx);
yyy=max(yyy,x);
}
printf("%lld",max(s-xxx,yyy-z));
return 0;
}
```