题解 P2449 【[SDOI2005]矩形】
Ajwallet
·
·
题解
大意
# 思路
其实楼下的题解更加通俗易懂，但是有些过于繁琐，判断语句其实只需要用三行就可以了。而且操作可以边输入边做，节省循环。
思路较为简单，就是判断两个矩形是否重叠，如果重叠则用并查集将它们合并。
最后判断有哪几个元素的祖先就是自己（即有几个联通分量）
# 代码
```
#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);//输出
}
```