sdnu 1016.矩形合并 (并查集)

Description

平面上有n个矩形，给定每个矩形的左下角坐标和右上角坐标。如果把重合的矩形合并成一个图形，则经过合并之后，还剩多少个图形？

Input

第1行：一个整数n(1 <= n <= 100)，表示矩形的数量。
第2至第n+1行：每行有4个整数(不会超过int)，第i 行中的4个数字分别表示编号为i-1的矩形的左下角x、y坐标与右上角x、y坐标。

Output

合并后剩余的图形数。

Sample Input

3
0 0 2 2
1 1 4 4
4 4 5 5

Sample Output

2

Hint

相邻不重合的图形不合并

Source

SDNU ACM-ICPC 2010复赛(2009级)

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=120;
struct node
{
int x1,x2,y1,y2;
}s[N];
int a[120];
bool judge(node a,node b)
{
if(a.x1<b.x2&&a.y1<b.y2&&a.x2>b.x1&&a.y2>b.y1)
return 1;
return 0;
}
int Find(int x)
{
if(a[x]!=x)
{
a[x]=Find(a[x]);
}
return a[x];
}
void unionn(int x,int y)
{
int xx=Find(x);
int yy=Find(y);
if(xx!=yy)
{
a[xx]=yy;
}
}
//int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);}
//void unionn(int x, int y){fa[Find(x)] = fa[Find(y)];}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
a[i]=i;
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(judge(s[i],s[j]))
{
unionn(i,j);
}
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]==i)
++cnt;
}
cout<<cnt<<'n';
}
return 0;
}

最后

以上就是发嗲草莓为你收集整理的sdnu 1016.矩形合并 (并查集)的全部内容，希望文章能够帮你解决sdnu 1016.矩形合并 (并查集)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。