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;
- }
来源: http://www.bubuko.com/infodetail-3003230.html