题解：P15058 [UOI 2023 II Stage] Rectangles are everywhere

__Wanna__Accepted__ · 2026-01-26 14:18:43 · 题解

题解

还是并查集。显然我们要把所有相连的矩形合并成一个连通块，判定式子比较复杂但稍微推一下就有了。

考虑什么样的连通块会挡住 Andriyko 的路。发现当且仅当它既与大矩形的左或上边相连，又与大矩形的右或下边相连。于是我们维护每个矩形的这两个条件，然后也用并查集合并到一起，最后只要存在一个连通块同时满足这两个条件，Andriyko 就会被挡住了。

代码

#include<iostream>
using namespace std;
const int N=5001;
int n,m,k,x1[N],x2[N],y1[N],y2[N],f[N];
bool p1[N],p2[N];
int find(int x){
    return (f[x]==x)?x:(f[x]=find(f[x]));
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)f[i]=i;
    for(int i=1;i<=k;i++){
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        if(x1[i]==0||y2[i]==m)p1[i]=1;
        if(x2[i]==n||y1[i]==0)p2[i]=1;
        for(int j=1;j<i;j++){
            if(
                (x1[i]<=x1[j]&&x1[j]<=x2[i]||x1[j]<=x1[i]&&x1[i]<=x2[j])&&
                (y1[i]<=y1[j]&&y1[j]<=y2[i]||y1[j]<=y1[i]&&y1[i]<=y2[j])
            ) f[find(i)]=find(j);
        }
    }
    for(int i=1;i<=k;i++){
        if(p1[i])p1[find(i)]=1;
        if(p2[i])p2[find(i)]=1;
    }
    for(int i=1;i<=k;i++){
        if(p1[i]&&p2[i]){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}