自动搬运

查看原文

来自洛谷，原作者为

	HAPPINESS23333 HAPPY HAPPY HAPPY~DENG DENG DENG DENG DENG DENG~HAPPY HAPPY HAPPY HAPPY HAPPY HAPPY~~~~~(=´∇｀=) ～♪(灌注必回)

搬运于2025-08-24 23:14:52，当前版本为作者最后更新于2025-05-05 12:52:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

核心思路

通过观察暴力的实现，可以发现关键点在于如何快速计算所有矩形对的极值。

先明确定义：两个点 $(a,b)$ 和 $(c,d)$ 的切比雪夫距离为 $\max(|a-c|,|b-d|)$。

两个矩形的距离定义为各在内部（包括四条边上）任取一点的切比雪夫距离的最小值。

接下来，我们根据暴力思想的步骤逐步优化。

1. 根据定义我们知道，两矩形的最小距离为两个方向间隔的最大值。故问题转化为如何求某一坐标轴上对距离的贡献。显然有两种情况：

   • 两矩形在某一坐标轴上有重叠，该方向的距离贡献为 $0$。
   • 反之，则距离贡献为该轴方向上的间隔。

2. 接下来要求全局最大值。最终的全局最大值是 $x$ 和 $y$ 方向最大间隔的较大者。显然，最大 $x$ 方向间隔只有两种情况：

   • 某个矩形的左边界极大，另一矩形的右边界极小。
   • 某个矩形的右边界极大，另一矩形的左边界极小。

$y$ 方向同理。具体实现可以看代码。

来，上代码

#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;
}