题解：P12351 「HCOI-R2」哀之距

题目传送门

核心思路

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

先明确定义：两个点

(a,b)

和

(c,d)

的切比雪夫距离为

\max(|a-c|,|b-d|)

。

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

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

根据定义我们知道，两矩形的最小距离为两个方向间隔的最大值。故问题转化为如何求某一坐标轴上对距离的贡献。显然有两种情况：
- 两矩形在某一坐标轴上有重叠，该方向的距离贡献为 $0$ 。
- 反之，则距离贡献为该轴方向上的间隔。
接下来要求全局最大值。最终的全局最大值是 $x$ 和 $y$ 方向最大间隔的较大者。显然，最大 $x$ 方向间隔只有两种情况：
- 某个矩形的左边界极大，另一矩形的右边界极小。
- 某个矩形的右边界极大，另一矩形的左边界极小。

y

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

来，上代码

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

题解：P12351 「HCOI-R2」哀之距

文章操作

核心思路

来，上代码

相关推荐

评论

题解：P12351 「HCOI-R2」哀之距