题解：P12351 「HCOI-R2」哀之距
HAPPINESS23333
·
·
题解
题目传送门
核心思路
通过观察暴力的实现，可以发现关键点在于如何快速计算所有矩形对的极值。
先明确定义：两个点 (a,b) 和 (c,d) 的切比雪夫距离为 \max(|a-c|,|b-d|)。
两个矩形的距离定义为各在内部（包括四条边上）任取一点的切比雪夫距离的最小值。
接下来，我们根据暴力思想的步骤逐步优化。
-
根据定义我们知道，两矩形的最小距离为两个方向间隔的最大值。故问题转化为如何求某一坐标轴上对距离的贡献。显然有两种情况：
- 两矩形在某一坐标轴上有重叠，该方向的距离贡献为 0。
- 反之，则距离贡献为该轴方向上的间隔。
-
接下来要求全局最大值。最终的全局最大值是 x 和 y 方向最大间隔的较大者。显然，最大 x 方向间隔只有两种情况：
- 某个矩形的左边界极大，另一矩形的右边界极小。
- 某个矩形的右边界极大，另一矩形的左边界极小。
---
### 来，上代码
```cpp
#include<bits/stdc++.h>
//这里我把long long改成ll了awa
#define ll long long
using namespace std;
int main(){
int n;
cin>>n;
//初始化极值变量
//mx0=所有矩形左边界最大值（对应x0的max）
//mx1=所有矩形右边界最小值（对应x1的min）
//my0=所有矩形下边界最大值（对应y0的max）
// my1=所有矩形上边界最小值（对应y1的min）
ll mx0=LLONG_MIN,mx1=LLONG_MAX;
ll my0=LLONG_MIN,my1=LLONG_MAX;
//遍历所有矩形，更新极值（注意：仅处理了单方向间隔）
for(int i=0;i<n;i++){
ll x0,y0,x1,y1;
cin>>x0>>y0>>x1>>y1;
//更新x方向极值
if(x0>mx0){//维护最大左边界
mx0=x0;
}
if(x1<mx1){//维护最小右边界
mx1=x1;
}
//更新y方向极值
if(y0>my0){//维护最大下边界
my0=y0;
}
if(y1<my1){//维护最小上边界
my1=y1;
}
}
//计算单方向间隔
ll dx=mx0-mx1;//最大左边界-最小右边界
ll dy=my0-my1;//最大下边界-最小上边界
//最终结果
ll ans=max(max(dx,dy),0LL);
cout<<ans<<endl;
return 0;
}
```