记录编号	553000	评测结果	AAAAAAAAAA
题目名称	岛国	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2020-08-10 14:45:23	内存使用	2.06 MiB

#include<cstdio>
#include<algorithm>

using namespace std;
const int maxN = 5e3 + 10;

int n,ans,f[maxN];

struct land{
	int x1,x2,y1,y2;
	bool operator <(const land& b)const{
	    return x1 < b.x1;
    }
    int intersec(land b){
	    if (y1 - 1 > b.y2 || b.y1 - 1 > y2)
            return -1;
	    if (y1 - 1 == b.y2 || b.y1 - 1 == y2)
            return 0;
        else
            return 1;
    }
}lan[maxN];

int get(int x);
void merge(int a,int b);
bool intersed(int a,int b);

int main(){
	freopen("jx.in","r",stdin);
	freopen("jx.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1;i <= n;i ++){
		f[i] = i;
		scanf("%d%d%d%d",&lan[i].x1,&lan[i].y1,&lan[i].x2,&lan[i].y2);
	}
	ans = n; 
	sort(lan + 1,lan + n + 1);
	for (int i = 1;i < n;++ i){
		for (int j = i + 1;lan[i].x2 + 1 >= lan[j].x1 && j <= n;j ++){
			if (lan[i].x2 + 1 == lan[j].x1){
				if (lan[i].intersec(lan[j]) == 1 && get(i) != get(j)){
					merge(i,j);
					ans --;
				}
			}
			else {
				if(lan[i].intersec(lan[j]) != -1 && get(i) != get(j)){
					merge(i,j);
					ans --;
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

int get(int x){
	if (x == f[x])
        return x;
	else 
        return f[x] = get(f[x]);
}

void merge(int a,int b){
	f[get(a)]=get(b);
}

bool intersed(int a,int b){
	return get(a) == get(b);
}