随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 1177 Picture

题目链接:http://poj.org/problem?id=1177
/*
题意:
    给定N(N <= 5000)个矩形纸片,求它们重叠后外围轮廓的周长。

解法:
线段树

思路:
    矩形面积并的变形,其实只需要修改Update函数即可,在线段树的
结点中保存一个nCover域,表示当前插入的线段覆盖的次数,yCount表
示当前y方向的长度的段数,LeftConnect和RightConnect表示当前结点
的线段两端点是否和父亲结点的区间的左右端点连接,之后的工作就是
在插入线段的时候随即更新这些信息就可以了。
    然后统计周长的时候x方向和y方向都做一遍,其中一维线性枚举,
另一维通过线段树区间插入,外轮廓的周长就是每次相邻矩形统计的时
候 线段树根结点的段数*2*相邻矩形边的差 的总和。
    Update函数的更新如下:
    void Tree::Update() {
    if(nCover) {
        // 当前区间的线段被完全覆盖
        yCount = 1;
        LeftConnect = RightConnect = true;
    }else {
        if(l + 1 == r) {
            // 叶子结点的区间,并且未被覆盖
            yCount = 0;
            LeftConnect = RightConnect = false;
        }else {
            // 内部结点所在区间,根据子树的情况统计信息
            LeftConnect = T[root<<1].LeftConnect;
            RightConnect = T[root<<1|1].RightConnect;
            yCount = T[root<<1].yCount + T[root<<1|1].yCount - 
                ((T[root<<1|1].LeftConnect*T[root<<1].RightConnect)?1:0);
        }
    }
*/


#include 
<iostream>
#include 
<vector>
#include 
<algorithm>
using namespace std;

#define maxn 20010

struct VLine {
    
int x;
    
int y0, y1;
    
int val;
    VLine() 
{}
    VLine(
int _x, int _y0, int _y1, int _val) {
        x 
= _x; 
        y0 
= _y0;
        y1 
= _y1;
        val 
= _val;
    }

}
;
vector 
<VLine> Vl[2];

bool cmp(VLine a, VLine b) {
    
return a.x < b.x;
}


struct Tree {
    
int root, l, r;
    
int nCover;
    
int ylen;
    
int yCount;
    
bool LeftConnect, RightConnect;

    
void Update();
}
T[ maxn*4 ];

void Tree::Update() {
    
if(nCover) {
        ylen 
= r - l;
        yCount 
= 1;
        LeftConnect 
= RightConnect = true;
    }
else {
        
if(l + 1 == r) {
            ylen 
= 0;
            yCount 
= 0;
            LeftConnect 
= RightConnect = false;
        }
else {
            ylen 
= T[root<<1].ylen + T[root<<1|1].ylen;
            LeftConnect 
= T[root<<1].LeftConnect;
            RightConnect 
= T[root<<1|1].RightConnect;
            yCount 
= T[root<<1].yCount + T[root<<1|1].yCount - 
                ((T[root
<<1|1].LeftConnect*T[root<<1].RightConnect)?1:0);
        }

    }

}



void Build(int root, int l, int r) {
    T[root].l 
= l;
    T[root].r 
= r;
    T[root].root 
= root;
    T[root].nCover 
= T[root].ylen = T[root].yCount = 0;
    T[root].LeftConnect 
= T[root].RightConnect = false;
    
if(l + 1 == r) {
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(root
<<1, l, mid);
    Build(root
<<1|1, mid, r);
}


void Insert(int root, int l, int r, int val) {
    
if(T[root].l >= r || l >= T[root].r)
        
return ;

    
if(l <= T[root].l && T[root].r <= r) {
        T[root].nCover 
+= val;
        T[root].Update();
        
return ;
    }


    Insert(root
<<1, l, r, val);
    Insert(root
<<1|1, l, r, val);

    T[root].Update();
}


int n;
int main() {
    
int i, j;
    
while(scanf("%d"&n) != EOF) {
        Vl[
0].clear();
        Vl[
1].clear();
        
for(i = 0; i < n; i++{
            
int x0, y0, x1, y1;
            scanf(
"%d %d %d %d"&x0, &y0, &x1, &y1);
            x0 
+= 10000; y0 += 10000;
            x1 
+= 10000; y1 += 10000;
            Vl[
0].push_back( VLine(x0, y0, y1, 1) );
            Vl[
0].push_back( VLine(x1, y0, y1, -1) );

            Vl[
1].push_back( VLine(y0, x0, x1, 1) );
            Vl[
1].push_back( VLine(y1, x0, x1, -1) );
        }
    
        
int ans = 0;

        
for(j = 0; j < 2; j++{
            sort(Vl[j].begin(), Vl[j].end(), cmp);
            Build(
1020000);
            
for(i = 0; i < Vl[j].size(); i++{
                
if(i) {
                    ans 
+= 2 * (Vl[j][i].x - Vl[j][i-1].x) * T[1].yCount;
                }

                Insert(
1, Vl[j][i].y0, Vl[j][i].y1, Vl[j][i].val);
            }

        }

        printf(
"%d\n", ans);
    }

    
return 0;
}

posted on 2011-04-03 21:13 英雄哪里出来 阅读(1341) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理