链接：http://vjudge.net/problem/viewProblem.action?id=49408
题意：在平面内给出若干个矩形，求出它们能将整个平面分成多少份。
思路：刚開始一眼看到认为是几何题，可是发现最多仅仅有50个矩形后，灵光一闪认为直接离散化再暴力就能够了。把全部矩形的x,y坐标分别离散化，而且为了防止出现离散的太近导致矩形之前没有空隙的情况，将全部点离散化的坐标记作偶数坐标。然后DFS找到全部矩形之间的空隙。
代码：
#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int vis[220][220];
int ans=0;
int tot;
int lenx,leny;
int dfs2(int x,int y)
{
if(vis[x][y]==0)
{
vis[x][y]=1;
for(int i=0; i<4; i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=0&&nx<lenx*2+4&&ny>=0&&ny<leny*2+4)
{
dfs2(nx,ny);
}
}
}
}
int dfs1(int x,int y)
{
if(vis[x][y]==0)
{
vis[x][y]=1;
ans++;
for(int i=0; i<4; i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=0&&nx<lenx*2+4&&ny>=0&&ny<leny*2+4)
dfs2(nx,ny);
}
}
}
int main()
{
int aa[100][4];
int x[220],y[220],top_x=0,top_y=0;
while(scanf("%d",&tot)&&tot)
{
top_x=top_y=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(aa,0,sizeof(aa));
memset(vis,0,sizeof(vis));
ans=0;
for(int i=0; i<tot; i++)
{
scanf("%d%d%d%d",&aa[i][0],&aa[i][1],&aa[i][2],&aa[i][3]);
x[top_x++]=aa[i][0];
x[top_x++]=aa[i][2];
y[top_y++]=aa[i][1];
y[top_y++]=aa[i][3];
}
sort(x,x+tot*2);
sort(y,y+tot*2);
lenx=unique(x,x+tot*2)-x;
leny=unique(y,y+tot*2)-y;
for(int i=0; i<tot; i++)
{
for(int j=0; j<lenx; j++)
{
if(aa[i][0]==x[j])
{
aa[i][0]=j*2+2;
break;
}
}
for(int j=0; j<lenx; j++)
{
if(aa[i][2]==x[j])
{
aa[i][2]=j*2+2;
break;
}
}
for(int j=0;j<leny;j++)
{
if(aa[i][1]==y[j])
{
aa[i][1]=j*2+2;
break;
}
}
for(int j=0;j<leny;j++)
{
if(aa[i][3]==y[j])
{
aa[i][3]=j*2+2;
break;
}
}
}
for(int i=0; i<tot; i++)
{
for(int j=aa[i][0]; j<=aa[i][2]; j++)
{
vis[j][aa[i][1]]=1;
vis[j][aa[i][3]]=1;
}
for(int j=aa[i][3]; j<=aa[i][1]; j++)
{
vis[aa[i][0]][j]=1;
vis[aa[i][2]][j]=1;
}
}
for(int i=0; i<lenx*2+4; i++)
{
for(int j=0; j<leny*2+4; j++)
{
if(vis[i][j]==0)
dfs1(i,j);
}
}
printf("%d
",ans);
}
return 0;
}