自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:37:49，当前版本为作者最后更新于2018-03-22 15:39:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大意

$n$个矩形，给定每个矩形的左下角和右上角的坐标。若两个矩形有叠在一起的部分视为它们为一个联通分量，问有几个联通分量。

思路

其实楼下的题解更加通俗易懂，但是有些过于繁琐，判断语句其实只需要用三行就可以了。而且操作可以边输入边做，节省循环。

思路较为简单，就是判断两个矩形是否重叠，如果重叠则用并查集将它们合并。

最后判断有哪几个元素的祖先就是自己（即有几个联通分量）

代码

#include<cstdio>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int f[7001],n,ans;
struct node
{
    int x1,y1,x2,y2;
}v[7001];//(x1,y1)为左下角的坐标，(x2,y2)为右上角的坐标
int find(int x){return x==f[x]?x:f[x]=find(f[x]);};//查找祖先
void judge(int x,int y){f[find(x)]=find(y);};//合并
bool check(node x,node y)//判断
{
    if((x.x2<y.x1||y.x2<x.x1)||(x.y2<y.y1||y.y2<x.y1)) return false;//y矩形左上角的横坐标小于x矩形左下角的横坐标或大于x矩形右上角的横坐标则false；y矩形左上角的纵坐标小于x矩形左下角的纵坐标或大于x矩形右上角的横坐标则false
    if((x.x1==y.x2||x.x2==y.x1)&&(x.y1==y.y2||x.y2==y.y1)) return false;//这个是特判，当两个矩形出现相交但不重叠的情况放回false；
    return true;//否则是true；
}
int main()
{
    scanf("%d",&n);
    r(i,1,n)
    {
     	scanf("%d%d%d%d",&v[i].x1,&v[i].y1,&v[i].x2,&v[i].y2),f[i]=i;//输入+并查集初始化
     	r(j,1,i-1)//与之前所有矩形判断
      	 if(check(v[i],v[j])&&find(i)!=find(j))//满足条件且不再一个联通分量
       	  judge(i,j);//合并
    }
    r(i,1,n) ans+=f[i]==i;//求出答案
    printf("%d",ans);//输出
}