posts - 64, comments - 4, trackbacks - 0, articles - 0

题意: 就是求重叠的矩阵轮廓的周长。
总结:理解线段树最好的方法就是利用样例,或者自己利用模型模拟一遍,然后就是边模拟边想代码的实现。
             我的写法是比较正规的二叉树的形式,各个节点描述信息如下。
  这个程序经典在于涵盖了线段树的基本操作和节点记录的数据,至于求矩阵面积交,只是缺少了扫描线区间个数的记录,这也是求矩阵周长并的关键。
 具体cpp代码如下:


//poj1177Pucture线段树 
#include <cstdio>
#include 
<algorithm>
#include 
<stdlib.h>
using namespace std;
const int root = 0
;

struct
 Node{
       
int
 l,r;
       
int cover,len,lines;//vover记录覆盖次数,len长度,lines记录并区间数 

       int lf,rf;//记录左右节点是否被覆盖 
       int lnd,rnd;//记录左右节点 
}node[20005];
int
 cnt,cnty;
int indexy[10010];//离散纵坐标y的数组 


struct Cord{
       
int
 x,y1,y2;
       
bool
 f;
}cord[
10005];//竖线 

int n;

void Creat(int p,int l,int
 r)
{
     node[p].l 
= l;   node[p].r =
 r;
     node[p].lf 
= node[p].rf = 0
;
     node[p].len 
= node[p].lines = 0
;
     
if (r - l > 1
)
     {
           
int mid = (r+l) >> 1
;
           node[p].lnd 
= ++
cnt;
           Creat(cnt,l,mid); 
//递归创建左子树 

           node[p].rnd = ++cnt;
           Creat(cnt,mid,r);
//递归创建右子树 

     }
     
else
 {
            node[p].lnd 
= node[p].rnd = -1
;
          }
}

void upData(int p)  //每次插入或删除后的更新操作

{
     
if (node[p].cover > 0)  //整条线段被覆盖

     {
        node[p].len 
= indexy[node[p].r] -
 indexy[node[p].l];
        node[p].lines 
= 1
;
        node[p].lf 
= node[p].rf = 1
;
     }
     
else if (node[p].l == node[p].r - 1//未被覆盖的元线段 

          {
                node[p].lf 
= node[p].rf = 0
;
                node[p].len 
= node[p].lines = 0
;
          }
          
else {                                 //未被覆盖的非元线段 

                 int left = node[p].lnd;
                 
int right =
 node[p].rnd;
                 node[p].lf 
=
 node[left].lf;
                 node[p].rf 
=
 node[right].rf;
                 node[p].len 
= node[left].len +
 node[right].len;
                 node[p].lines 
= node[left].lines + node[right].lines - node[left].rf*
node[right].lf;
               }
}

void Insert(int p,int l,int r) //插入线段 

{
     
if (l <= node[p].l && node[p].r <=
 r)
        node[p].cover 
++
;
     
else
 {
             
int mid = (node[p].l+node[p].r) >> 1
;
              
             
if (mid >
 l)
                Insert(node[p].lnd,l,r);
             
if (mid <
 r)
                Insert(node[p].rnd,l,r);     
          }
          
     upData(p);
}

void Delete(int p,int l,int r) //删除线段 

{
     
if (l <= node[p].l && node[p].r <=
 r)
     {
         node[p].cover 
--

     }   
     
else
 {
             
int mid = (node[p].l+node[p].r) >> 1
;
             
if (mid >
 l)
                Delete(node[p].lnd,l,r);
             
if (mid <
 r)
                Delete(node[p].rnd,l,r);     
          }
     upData(p);
}

bool cmp(const Cord &a,const Cord &
b)
{
     
return a.x <
 b.x;
}

void init_index() //对纵坐标离散去重 

{
     sort(indexy
+1,indexy+1+
cnty);
     
int m = 1
;
     
for (int i = 2; i <= cnty; i++
)
     {
         
if (indexy[i] != indexy[i-1
])
         {
            m
++
;
            indexy[m] 
=
 indexy[i];
         }
     }
     cnty 
=
 m;
}

int Bi_search(int key) //二分查找 y 对应的离散坐标 

{
    
int l = 1,r = cnty + 1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if (indexy[mid] ==
 key)
             
return
 mid;
          
if (indexy[mid] <
 key)
             l 
= mid + 1
;
          
else r =
 mid;
    }
}

int
 main()
{
    
int
 i,j,left,right,prelen,prelines;
    
int
 x1,x2,y1,y2;
    
int
 ans;
    
while (scanf("%d",&n) !=
 EOF)
    {
          
for (i = 1;i <= n + n;  i+=2
)
          {
              scanf(
"%d %d %d %d",&x1,&y1,&x2,&
y2);
              cord[i].x 
= x1; cord[i].y1 = y1; cord[i].y2 =
 y2; 
              cord[i].f 
= true
;
              cord[i
+1].x = x2; cord[i+1].y1 = y1; cord[i+1].y2 =
 y2;
              cord[i
+1].f = false
;
              indexy[i] 
=
 y1;
              indexy[i
+1=
 y2;
          }
          
          sort(cord
+1,cord+1+n+
n,cmp);
          cnty 
= n+
n;
          init_index();
          cnt 
= 0
;
          Creat(root,
1
,cnty);
          
          left 
= Bi_search(cord[1
].y1);
          right 
= Bi_search(cord[1
].y2);
              
          Insert(root,left,right);
          prelen 
=
 node[root].len; 
          prelines 
=
 node[root].lines;
          ans 
=
 prelen;
          
          
for (i = 2; i <= n+n; i++
)
          {
              left 
=
 Bi_search(cord[i].y1);
              right 
=
 Bi_search(cord[i].y2);
               
              
if
 (cord[i].f)
                   Insert(root,left,right);
              
else
 {
                    Delete(root,left,right);
                   }
              ans 
+= abs(prelen - node[root].len); //纵向周长增长量为前后两次被覆盖线段长度的改变量 

              ans += prelines*(cord[i].x - cord[i-1].x)*2//横向周长的增长量为上一次区间个数乘2在乘横向长度
              prelen = node[root].len;
              prelines 
=
 node[root].lines;
          }
          printf(
"%d\n"
,ans);
    }
    
return 0
;
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理