Description

在平面上堆叠着若干矩形，这些矩形的四边与平面X坐标轴或Y坐标轴平行。下图展示了其中一种情况，3个矩形的边将平面划分成8个区域：


下面展示了另一种稍稍复杂一些的情况：

你的任务是写一个程序，判断这些矩形将平面分成了几个区域。

Input

        输入的第一行是一个正整数n（n<=50），分别矩形的数目，接下来的n行，每行有4个用空格分隔的整数li,ti,ri,bi（1<=i<=n）代表了第i个矩形的坐标，（li,ti）代表该矩形左上角的X坐标和Y坐标，(ri,bi)代表该矩形右下角的X坐标和Y坐标，0<=li<ri<=10^6，0<=bi<ti<=10^6）。

Output

输出只有一个整数，代表这些矩形将平面划分成多少区域。

Sample Input

Sample Input1
3
4 28 27 11
15 20 42 5
11 24 33 14

Sample Input2
5
4 28 27 11
12 11 34 2
7 26 14 16
14 16 19 12
17 28 27 21
 

Sample Output

Sample Output1
8

Sample Output2
6

Solution

对于每个矩形离散化，然后对每个区域进行染色，找出不同颜色的个数即可。

注意细节：

1.离散化时相邻两个数差值为2，为了保证左右两条边的x坐标或y坐标只相差1的矩形，因为dg的是整数坐标，所以中间的部分要扩大。并且最小的离散后的数为2，这是保证边界为1的时候能够联通；同理，最大到202，因此界限应规定为203。

2.计算答案的时候不能只算所有矩形内部的答案最后再+1，应该用整个203*203的平面去跑。原因是可能四个矩形围成一圈又构成了一个新的矩形，这个新矩形的每一条边分别由一个矩形的不同的边来提供。这时中间的部分就算不到了，如下图：

Code

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
#define N 110
using namespace std;
I n,tot,now,ans=0,bz[2010][2010],fx[4][2]={
  {0,1},{1,0},{-1,0},{0,-1}};
struct node{I x1,y1,x2,y2;}p[N<<1];
struct point{I v,t,id;}a[N<<1];
char c;
void R(I &x){
	x=0;I w=1;c=getchar();
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	x*=w;
}
void dg(I x,I y){
	bz[x][y]=1;
	F(l,0,3){
		I xx=x+fx[l][0],yy=y+fx[l][1];
		if(xx&&yy&&xx<=203&&yy<=203&&(!bz[xx][yy])) dg(xx,yy);
	}
}
I cmp(point x,point y){
	return x.v<y.v;
}
I main(){
	freopen("regions.in","r",stdin);
	freopen("regions.out","w",stdout);
	R(n);
	F(i,1,n){
		R(p[i].x1),R(p[i].y2),R(p[i].x2),R(p[i].y1);
		a[++tot]=point{p[i].x1,1,i};
		a[++tot]=point{p[i].x2,2,i};
	}
	sort(a+1,a+1+tot,cmp);
	now=2;
	F(i,1,tot){
		if(a[i].v!=a[i-1].v) now+=2;
		if(a[i].t==1) p[a[i].id].x1=now;
		else p[a[i].id].x2=now;
	}
	
	tot=0;
	F(i,1,n){
		a[++tot]=point{p[i].y1,1,i};
		a[++tot]=point{p[i].y2,2,i};
	}
	sort(a+1,a+1+tot,cmp);
	now=2;
	F(i,1,tot){
		if(a[i].v!=a[i-1].v) now+=2;
		if(a[i].t==1) p[a[i].id].y1=now;
		else p[a[i].id].y2=now;
	}
	
	F(i,1,n){
		F(j,p[i].x1,p[i].x2) bz[j][p[i].y1]=bz[j][p[i].y2]=1;
		F(j,p[i].y1,p[i].y2) bz[p[i].x1][j]=bz[p[i].x2][j]=1;
	}
	F(i,1,203){
		F(j,1,203){
			if(!bz[i][j]){
				dg(i,j);
				ans++;
			}
		}
	}
	
	printf("%d\n",ans);
	return 0;
}