记录编号	53125	评测结果	AAAAAAAAAA
题目名称	岛国	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.763 s
提交时间	2013-02-21 16:10:36	内存使用	3.17 MiB

#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
class Rectangle{
public:
	int minx,maxx;
	int miny,maxy;
}rec[5001];
bool adj_rec(Rectangle a,Rectangle b){
	if(a.minx>b.maxx+1||a.maxx<b.minx-1||a.miny>b.maxy+1||a.maxy<b.miny-1) return 0;
	if(a.minx==b.maxx+1){
		if(a.miny==b.maxy+1) return 0;
		if(a.maxy==b.miny-1) return 0;
	}
	if(a.maxx==b.minx-1){
		if(a.miny==b.maxy+1) return 0;
		if(a.maxy==b.miny-1) return 0;
	}
	return 1;
}
deque<int> c[5001];
bool visit[5001]={0};
int n;
void DFS(int x){
	visit[x]=true;
	int i;
	for(i=0;i<c[x].size();i++){
		if(visit[c[x][i]]) continue;
		DFS(c[x][i]);
	}
}
void output(void){
	int ans=0;
	int i;
	for(i=0;i<n;i++){
		if(!visit[i]){
			ans++;
			DFS(i);
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("jx.in","r",stdin);
	freopen("jx.out","w",stdout);
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++){
		scanf("%d%d%d%d",&rec[i].minx,&rec[i].miny,&rec[i].maxx,&rec[i].maxy);
		for(j=0;j<i;j++){
			if(adj_rec(rec[i],rec[j])) c[i].push_back(j),c[j].push_back(i);
		}
	}
	output();
	return 0;
}