记录编号	382277	评测结果	AAAAAAAAAAA
题目名称	[POI 1998] 相交的矩形	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-03-13 17:13:33	内存使用	0.51 MiB

//234.[POI1998]相交的矩形  \
g++ 234.[POI1998]相交的矩形.cpp -ggdb -D LOCAL -D debug

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

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MAXN 10000

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;
}

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("pro.in", "r", stdin);
	freopen("pro.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; j<=N&& s[j].x1<=s[i].x2; ++j){
			if(Pan(s[i], s[j])&& Union(i, j)){
				--cnt;
			}
			if(cnt==1){
				putchar('1'); return 0;
			}
		}
	}
	
	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 i=Find(a), j=Find(b);
	if(i==j)return false;
	fa[i]=j;
	return true;
}

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