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++;
}
}
}
/*F(k,1,n){
F(i,p[k].x1+1,p[k].x2-1){
F(j,p[k].y1+1,p[k].y2-1) if(!bz[i][j]){
dg(i,j);
ans++;
}
}
}
printf("%d\n",ans+1);//′í?ó′ú??
*/
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/32762.html
標籤：其他