jzoj 6798. 【2014廣州市選day2】regions
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
輸出只有一個整數，代表這些矩形將平面劃分成多少區域。
Solution
這道題有兩個做法。
首先先將橫坐標縱坐標離散化。
第一個做法：
用並查集，將相連的塊連接起來，最後查有多少個塊
第二個做法：
將邊打上標記，將沒被打標記的點進行擴散，統計塊數
（作者用的是第一個做法）
Code
#include <cstdio>
#include <algorithm>
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int i,p,last,fa[500001],n,j,heng,shu,l,r,ans,u,v,bj[500001];
bool bz[1001][1001];
struct re{
int x1,x2,y1,y2;
}a[51];
struct node{
int a,pl;
}k[100001];
const int d[5][2]={{0,0},{-1,0},{1,0},{0,1},{0,-1}};
bool cmp(node x,node y){return x.a<y.a;}
bool rec(node x,node y){return (x.pl<y.pl)||(x.pl==y.pl && x.a<y.a);}
int gf(int x)
{
if (x==fa[x]) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
void ls()
{
sort(k+1,k+2*n+1,cmp);
p=0,last=0;
for (i=1;i<=n+n;i++)
{
if (k[i].a==k[i-1].a) k[i-1].a=last;else
{
k[i-1].a=last;
last=++p;
}
}
k[n+n].a=last;
sort(k+1,k+2*n+1,rec);
}
int main()
{
open("regions");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
k[i].a=a[i].x1;k[i+n].a=a[i].x2;
k[i].pl=k[i+n].pl=i;
}
ls();
heng=p*2;
for (i=1;i<=n;i++)
{
a[i].x1=k[2*i-1].a*2;a[i].x2=k[2*i].a*2;
}
for (i=1;i<=n;i++)
{
k[i].a=a[i].y1;k[i+n].a=a[i].y2;
k[i].pl=k[i+n].pl=i;
}
ls();
shu=p*2;
for (i=1;i<=n;i++)
{
a[i].y1=k[2*i-1].a*2;a[i].y2=k[2*i].a*2;
}
for (i=1;i<=n;i++)
{
l=a[i].x1;r=a[i].x2;
for (j=a[i].y1;j<=a[i].y2;j++)
bz[l][j]=bz[r][j]=1;
l=a[i].y1;r=a[i].y2;
for (j=a[i].x1;j<=a[i].x2;j++)
bz[j][l]=bz[j][r]=1;
}
for (i=0;i<=heng;i++)
{
for (j=0;j<=shu;j++)
fa[i*shu+j]=i*shu+j;
}
for (i=0;i<=heng;i++)
{
for (j=0;j<=shu;j++)
{
if (bz[i][j]) continue;
for (l=1;l<=4;l++)
{
if (i+d[l][0]<=heng && i+d[l][0]>=0 && j+d[l][1]<=shu && j+d[l][1]>=0)
{
if (!bz[i+d[l][0]][j+d[l][1]])
{
u=gf(i*shu+j);
v=gf((i+d[l][0])*shu+j+d[l][1]);
if(fa[v]!=u) fa[u]=v;
}
}
}
}
}
for (i=0;i<=heng;i++)
{
for (j=0;j<=shu;j++)
{
if (bz[i][j]) continue;
u=gf(i*shu+j);
if (!i || !j || i==heng || j==shu)
{
if (!bj[u])bj[u]=2;
if (bj[u]==1) bj[u]=2,ans--;
}
if (!bj[u])
{
bj[u]=1;
ans++;
}
}
}
printf("%d",ans+1);
return 0;
}
