题目链接:
http://www.acmicpc.sdnu.edu.cn/problem/show/1016
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int pre[100]; struct sss { int lx,ly,rx,ry; }l[105]; int find (int x) { if(pre[x]==x)return x; else return pre[x]=find(pre[x]); } void merge(int x,int y) { int xx=find(x); int yy=find(y); if(xx!=yy) pre[xx]=yy; } int panduan (sss x,sss y) { if(x.rx<=y.lx||x.ry<=y.ly||x.lx>=y.rx||x.ly>=y.ry)return 0; else return 1; } int main () { int n; cin >> n; for (int i=1;i<=n;i++) { pre[i]=i; cin >> l[i].lx >> l[i].ly >> l[i].rx >> l[i].ry; } for(int i=1;i<=n;i++) { for (int j=i+1;j<=n;j++) { if(panduan(l[i],l[j])==1) merge(i,j); } } int ans=0; for (int i=1;i<=n;i++) { if(pre[i]==i) ans++; } cout << ans << endl; return 0; }