矩形切割与动态统计问题的一些ACM例题

发布时间：2012-08-09 15:47:12

矩

形

切

割

与

动

态

统

计

问

题

矩形切割具体思想见薛矛的《解决动态统计问题的两把利刃 》

矩形切割例题：（POJ：2528、3277、1151、1389、1177）

POJ 2528：Mayor's poster

//题意：贴海报（后一张海报一定不会被前面的海报覆盖），海报覆盖区域用[x,y]区间表示，问最后有多少张海报是没被完全覆盖的。

Code：

∙ #include

∙ #include

∙ using namespace std;

∙ #define maxn 10005

∙

∙ struct NODE

∙ {

∙ int x,y;

∙ int ans;

∙ }node[maxn];

∙ int n;

∙

∙ void cover(int l,int r,int k,int c)

∙ {

∙ while(k<n&&(r<node[k].x||l>node[k].y)) //完全不覆盖

∙ k++;

∙

∙ if(k>=n) //if(k>=n||(r-l+1<=0))

∙ {

∙ node[c].ans+=r-l+1;

∙ return;

∙ }

∙

∙ if(l<node[k].x) //右边部分被覆盖

∙ {

∙ cover(l,node[k].x-1,k+1,c);

∙ //l=node[k].x;

∙ }

∙

∙ if(r>node[k].y) //左边部分被覆盖

∙ {

∙ cover(node[k].y+1,r,k+1,c);

∙ //r=node[k].y;

∙ }

∙ }

∙

∙ int main()

∙ {

∙ int t,i,j,sum;

∙ scanf("%d",&t);

∙ while(t--)

∙ {

∙ sum=0;

∙ memset(node,0,sizeof(node));

∙ scanf("%d",&n);

∙ for(i=0;i<n;i++)

scanf("%d%d",&node[i].x,&node[i].y);

∙ for(i=n-1;i>=0;i--)

cover(node[i].x,node[i].y,i+1,i);

∙ for(i=0;i<n;i++)

∙ if(node[i].ans>0)

∙ sum++;

∙ printf("%d\n",sum);

∙ }

∙ return 0;

∙ }

/*

Sample Input

1

5

1 4

2 6

8 10

3 4

7 10

Sample Output

4

*/

POJ 3277：City Horizon

//题意：一些大楼都在地平线上，求这些大楼倒影覆盖总面积。

//分析：水平线上被覆盖的部分肯定记录到高度大的部分，所以按大楼高度升序排序。

Code：

∙ #include

∙ #include

∙ #include

∙ using namespace std;

∙ #define maxn 40005

∙

∙ struct NODE

∙ {

∙ __int64 x1,x2,y,ans;

∙ }node[maxn];

∙ int n;

∙

∙ bool cmp(NODE a,NODE b)

∙ {

∙ if(a.y!=b.y)

∙ return a.y<b.y; //因为是面积和的问题，所以宽高的肯定应该放在后面，低的算被覆盖

∙ else

∙ {

∙ if(a.x2!=b.x2)

∙ return a.x2<b.x2;

∙ else

∙ return a.x1>b.x1;

∙ }

∙ }

∙

∙ void cover(__int64 l,__int64 r,int k,int c)

∙ {

∙ while(k<n&&(r<node[k].x1||l>node[k].x2))

∙ k++;

∙ if(k>=n||(r-l<=0))

∙ {

∙ node[c].ans+=r-l;

∙ return;

∙ }

∙ if(l<node[k].x1)

∙ cover(l,node[k].x1,k+1,c);

∙ if(r>node[k].x2)

∙ cover(node[k].x2,r,k+1,c);

∙ }

∙

∙ int main()

∙ {

∙ int i,j;

∙ memset(node,0,sizeof(node));

∙ scanf("%d",&n);

∙ for(i=0;i<n;i++)

∙ scanf("%I64d%I64d%I64d",&node[i].x1,&node[i].x2,&node[i].y);

∙ stable_sort(node,node+n,cmp);

∙ for(i=n-1;i>=0;i--)

∙ cover(node[i].x1,node[i].x2,i+1,i);

∙ __int64 sum=0;

∙ for(i=0;i<n;i++)

∙ if(node[i].ans>=1)

∙ sum+=node[i].ans*node[i].y;

∙ printf("%I64d\n",sum);

∙ }

/*

Sample Input

4

2 5 1 （数据分别为水平线上起点和终点，楼的高度）

9 10 4

6 8 2

4 6 3

Sample Output

16

*/

POJ 1151：Atlantis（矩形面积并）

//法1：离散化（本题数据量为100以内）。离散化后坐标纸上最大为100*100的网格，将被覆盖的网格标记为true，之后直接扫描统计即可。

Code：

∙ #include

∙ #include

∙ #include

∙ #include

∙ #include

∙ using namespace std;

∙ #define maxn 205

∙

∙ struct NODE

∙ {

∙ double x1,y1,x2,y2;

∙ }node[maxn];

∙ double x[maxn],y[maxn];

∙ bool map[maxn][maxn];

∙

∙ int main()

∙ {

∙ int n,i,j,k,t=0;

∙ while(scanf("%d",&n),n)

∙ {

∙ int m=0;

∙ for(i=0;i<n;i++)

∙ {

∙ scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);

∙ x[m]=node[i].x1;  y[m]=node[i].y1;

∙ m++;

∙ x[m]=node[i].x2;  y[m]=node[i].y2;

∙ m++;

∙ }

∙ //printf("m=%d\n",m);

∙ sort(x,x+m);

∙ sort(y,y+m);

∙

∙ memset(map,false,sizeof(map));

∙ int x1,x2,y1,y2;

∙ for(i=0;i<n;i++) //离散化

∙ {

∙ for(j=0;j<m;j++)

∙ if(fabs(x[j]-node[i].x1)<=1e-6)

∙ { x1=j; break; }

∙ for(j=0;j<m;j++)

∙ if(fabs(x[j]-node[i].x2)<=1e-6)

∙ {   x2=j; break; }

∙ for(j=0;j<m;j++)

∙ if(fabs(y[j]-node[i].y1)<=1e-6)

∙ { y1=j; break; }

∙ for(j=0;j<m;j++)

∙ if(fabs(y[j]-node[i].y2)<=1e-6)

∙ { y2=j; break; }

∙ for(j=x1;j<x2;j++)

∙ for(k=y1;k<y2;k++)

∙ map[j][k]=true;

∙ }

∙ printf("Test case #%d\n",++t);

∙ double ans=0.0;

∙ for(i=0;i<m-1;i++)

∙ for(j=0;j<m-1;j++)

∙ if(map[i][j]) //被覆盖的求出面积 ans+=(x[i+1]-x[i])*(y[j+1]-y[j]);

∙ printf("Total explored area: %.2lf\n\n",ans);

∙ }

∙ return 0;

∙ }

//法2：普通矩形切割法。将每个矩形着色，假设后面的矩形颜色一定不会被前面的矩形颜色覆盖。最后扫描个每种颜色覆盖的区域。总和便是所求。

Code：

∙ #include

∙ #include

∙ #include

∙ #include

∙ using namespace std;

∙ #define maxn 105

∙

∙ struct NODE

∙ {

∙ double x1,y1,x2,y2;

∙ int color;

∙ }node[maxn];

∙ double map[maxn];

∙ int n;

∙

∙ void cover(double x1,double y1,double x2,double y2,int c,int k)

∙ {

∙ while(k<n&&(x1>node[k].x2||x2<node[k].x1||y1>node[k].y2||y2<node[k].y1))//不相交

∙ k++;

∙ if(k>=n||(fabs(x2-x1)<1e-6)||(fabs(y2-y1)<1e-6))

∙ {

∙ map[c]+=(x2-x1)*(y2-y1);

∙ return;

∙ }

∙

∙ if(x1<=node[k].x1)//偏左

∙ {

∙ cover(x1,y1,node[k].x1,y2,c,k+1); //分割

∙ x1=node[k].x1; //剩余量

∙ }

∙ if(x2>=node[k].x2) //偏右

∙ {

∙ cover(node[k].x2,y1,x2,y2,c,k+1);

∙ x2=node[k].x2;

∙ }

∙ if(y1<=node[k].y1) //偏下

∙ {

∙ cover(x1,y1,x2,node[k].y1,c,k+1);

∙ y1=node[k].y1;

∙ }

∙ if(y2>=node[k].y2) //偏上

∙ {

∙ cover(x1,node[k].y2,x2,y2,c,k+1);

∙ y2=node[k].y2;

∙ }

∙ }

∙

∙ int main()

∙ {

∙ int i,t=0;

∙ while(scanf("%d",&n),n)

∙ {

∙ t++;

∙ for(i=0;i<n;i++)

∙ {

∙ scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);

∙ node[i].color=i; //假定染色

∙ map[i]=0.0;

∙ }

∙

∙ for(i=n-1;i>=0;i--)

∙ cover(node[i].x1,node[i].y1,node[i].x2,node[i].y2,node[i].color,i+1);

∙ double ans=0.0;

∙ for(i=0;i<n;i++)

∙ if(map[i]>1e-6)

∙ ans+=map[i];

∙ printf("Test case #%d\nTotal explored area: %.2lf\n\n",t,ans);

∙ }

∙ return 0;

∙ }

/*

Sample Input

2

10 10 20 20

15 15 25 25.5

0

Sample Output

Test case #1

Total explored area: 180.00

*/

POJ 1177：（矩形周长并，括号匹配+矩形切割）

//分析：（括号匹配）首先把矩形的上边界作为“左括号”边，下边界作为“右括号”边，然后上下排序。假定排完序之后是下面的状态：

(())()(()()(()))

考虑“最外侧”的括号的数量。显然上面的那个串是

(()) & () & (()()(()))

有六个最外侧括号，那么边界数量就是6。排序的复杂度O(nlogn)，对于上面的思路，针对横边来说，如果并不是完全包括的怎办，那就是将边分割成一些小段在用括号匹配。 括号匹配用到此题恰到好处即在于可以有效处理掉重复覆盖避免重复计算边的问题。因为先将每个矩形的上、下边附一个标号1、-1。而对于此题有一个性质是，无论矩形怎么覆盖，最终对于某一小段边一定会有一个对应的边存在。那么1、-1正好起到匹配的作用。

Code：

∙ #include

∙ #include

∙ #include

∙ using namespace std;

∙ #define maxn 10005

∙

∙

∙ struct NODE

∙ {

∙ int cankao,weizhi,st,en; //weizhi为表明匹配边

∙ }nodex[maxn],nodey[maxn];

∙ int mapx[2*maxn],mapy[2*maxn],lenx[maxn],leny[maxn],vist[maxn];

∙

∙ bool cmp(NODE n1,NODE n2) {  return n1.cankao<n2.cankao; }

∙

∙ int main()

∙ {

∙ int n,i,j,x1,y1,x2,y2;

∙ memset(mapx,0,sizeof(mapx));

∙ memset(mapy,0,sizeof(mapy));

∙ scanf("%d",&n);

∙ for(i=0;i<n;i++) //存信息

∙ {

∙ scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

∙ x1+=maxn;y1+=maxn;x2+=maxn;y2+=maxn;

∙ mapx[x1]=mapx[x2]=mapy[y1]=mapy[y2]=1;

∙ nodex[2*i].cankao=y1;    nodex[2*i].weizhi=1;

nodex[2*i].st=x1;        nodex[2*i].en=x2;

nodex[2*i+1].cankao=y2;  nodex[2*i+1].weizhi=-1;

nodex[2*i+1].st=x1;      nodex[2*i+1].en=x2;

∙ nodey[2*i].cankao=x1;    nodey[2*i].weizhi=1;

nodey[2*i].st=y1;        nodey[2*i].en=y2;

nodey[2*i+1].cankao=x2;  nodey[2*i+1].weizhi=-1;

nodey[2*i+1].st=y1;       nodey[2*i+1].en=y2;

∙ }

∙

∙ stable_sort(nodex,nodex+2*n,cmp);

∙ stable_sort(nodey,nodey+2*n,cmp);

∙

∙ int tmpx=0,tmpy=0,ans=0;

∙ for(i=0;i<2*maxn;i++)

∙ {

∙ if(mapx[i])

∙ {

∙ mapx[i]=tmpx;

∙ lenx[tmpx++]=i;

∙ }

∙ if(mapy[i])

∙ {

∙ mapy[i]=tmpy;

∙ leny[tmpy++]=i;

∙ }

∙ }

∙

∙ for(i=0;i<2*n;i++) //离散化

∙ {

∙ nodex[i].st=mapx[nodex[i].st];

∙ nodex[i].en=mapx[nodex[i].en];

∙ nodey[i].st=mapy[nodey[i].st];

∙ nodey[i].en=mapy[nodey[i].en];

∙ }

∙

∙ memset(vist,0,sizeof(vist));

∙ for(i=0;i<2*n;i++)

∙ for(j=nodex[i].st;j<nodex[i].en;j++)

∙ {

∙ vist[j]+=nodex[i].weizhi;

∙ if(vist[j]==0) //匹配成功

∙ ans+=lenx[j+1]-lenx[j];

∙ }

∙ memset(vist,0,sizeof(vist));

∙ for(i=0;i<2*n;i++)

∙ for(j=nodey[i].st;j<nodey[i].en;j++)

∙ {

∙ vist[j]+=nodey[i].weizhi;

∙ if(vist[j]==0)

∙ ans+=leny[j+1]-leny[j];

∙ }

∙ printf("%d\n",2*ans);

∙ return 0;

∙ }

/*

Sample Input

7

-15 0 5 10

-5 8 20 25

15 -4 24 14

0 -6 16 4

2 15 10 22

30 10 36 20

34 0 40 16

Sample Output

228

*/

矩形切割与动态统计问题的一些ACM例题

推荐内容

相关推荐