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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
const int inf =
0x3f3f3f3f;
const int maxn =
1e6;
#define ll long long
int sign[
1000+
8], v[
1000+
8];
int n;
struct node
{
int lx, ly, rx, ry;
} root[1000+
8];
int get(
int x)
{
if(x !=
sign[x])
{
sign[x] =
get(sign[x]);
}
return sign[x];
}
int bcj(
int x,
int y)
//判断他们是不是同一个祖先
{
int miao =
get(x), ying =
get(y);
if(miao != ying)
//如果还不是同一个祖先，就把他们并在一起
{
sign[miao] =
ying;
return 1;
}
return 0;
}
int unio(node a, node b)
//合并矩阵
{
if(a.lx >= b.rx || a.ly >=
b.ry)
return 0;
if(a.rx <= b.lx || a.ry <=
b.ly)
return 0;
return 1;
}
int main()
{
int sum =
0;
while(~scanf(
"%d", &n) &&
n)
{
fill(v, v+
1000+
8,
0);
for(
int i =
0; i<n; i++
)
{
sign[i] =
i;
scanf("%d%d%d%d", &root[i].lx, &root[i].ly, &root[i].rx, &
root[i].ry);
}
for(
int i =
0; i<n; i++
)
{
for(
int j = i+
1; j<n; j++
)
{
if(unio(root[i], root[j]))
//如果他们是同一个矩阵
bcj(i, j);
//合并这两玩意儿
}
}
for(
int i =
0; i<n; i++
)
v[get(i)] =
1;
//如果该矩阵已经被合并，就标记一下（记录他们最后指向的那个矩阵）
for(
int i =
0; i<n; i++
)
if(v[i] ==
1)
//如果那个矩阵（最后指向的那个矩阵）被标记了，就++
sum++
;
printf("%d\n", sum);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10617225.html
相关资源：JAVA上百实例源码以及开源项目
