ural1147(Shaping Regions)矩形切割 - c++编程基础

TOP

ural1147(Shaping Regions)矩形切割

2015-07-24 05:49:53 来源: 作者: 【大中小】浏览:4次

题意：一个10000*10000的矩阵，初始颜色都为1，然后最多2500次涂色，每次涂色将一个矩形的面积涂成某个特定颜色，问涂完之后每种颜色最终的面积。

解法：倒序计算，矩形切割

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               //freopen (in.txt , r , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=2510; const int INF=1e9+7; struct rec { int x1,x2,y1,y2; int color; } recs[Max]; int A,B; int n; int getans(int x1,int x2,int y1,int y2,int p) { while((p<=n)&&(x1>=recs[p].x2||x2<=recs[p].x1||y1>=recs[p].y2||y2<=recs[p].y1)) p++; if(p>n) return (x2-x1)*(y2-y1); int ans=0; if(x1
              
               recs[p].x2) ans+=getans(recs[p].x2,x2,y1,y2,p+1),x2=recs[p].x2; if(y2>recs[p].y2) ans+=getans(x1,x2,recs[p].y2,y2,p+1),y2=recs[p].y2; if(y1
               
                =1; i--) { int tool=getans(recs[i].x1,recs[i].x2,recs[i].y1,recs[i].y2,i+1); ans[recs[i].color]+=tool; ans[1]-=tool; } for(int i=1; i<=2500; i++) if(ans[i]) printf(%d %d ,i,ans[i]); } return 0; } /* 20 20 3 2 2 18 18 2 0 8 19 19 3 8 0 10 19 4 */


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C/C++中容器vector使用方法(第二..	下一篇：LeetCode――Integer to Roman

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: