记录编号	381344	评测结果	AAAAAAAAAA
题目名称	岛国	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2017-03-11 12:37:31	内存使用	0.41 MiB

//\
456.岛国\
g++ 456.岛国_1.cpp -g -O2 -D LOCAL -D debug

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define is_num(tmp) (tmp <= '9' and tmp >= '0')
inline int in(void){
	char tmp = getchar();
	int res = 0, f = 1;
	while(!(is_num(tmp) || tmp == '-'))tmp = getchar();
	if(tmp == '-')f = -1, tmp=getchar();
	while(is_num(tmp))
		res=(res<<1)+(res<<3)+(tmp^48),
		tmp=getchar();
	return res*f;
}

#define MAXN 5010

struct DATA{
	int x1,y1;
	int x2,y2;
	
	void get(void){
		x1=in(),y1=in(),
		x2=in(),y2=in();
		return ;
	}
	
	bool operator < (const DATA &a)const{
		return x1<a.x1;
	}
};

int Find(int);
bool Union(int, int);
bool Pan(const DATA&, const DATA&);

DATA s[MAXN];
int fa[MAXN];
int N, cnt;

int main(){
#ifndef LOCAL
	freopen("jx.in", "r", stdin);
	freopen("jx.out", "w", stdout);
#endif

	cnt=N=in();
	for(int i=1; i<=N; ++i){
		fa[i]=i;
		s[i].get();
	}
	sort(s+1,s+1+N);

	for(int i=1; i<N; ++i){
		for(int j=i+1;s[j].x1<=s[i].x2+1&&j<=N; ++j){
			if(Pan(s[i], s[j])&&Union(i, j)){
				--cnt;
			}
		}
	}

	printf("%d",cnt);
	return 0;
}

int Find(int i){
	if(fa[i]!=i)fa[i]=Find(fa[i]);
	return fa[i];
}

bool Union(int a, int b){
	int ii=Find(a), jj=Find(b);
	if(ii==jj)return false;
	fa[ii]=jj;
	return true;
}

bool Pan(const DATA& a, const DATA& b){
	if(a.y1-1>b.y2||b.y1-1>a.y2)return false;
	if(a.x2+1==b.x1){
		if(a.y1-1==b.y2||b.y1-1==a.y2)return false;
		else return true;
	}
	else return true;
}