POJ 1177 Picture（线段树：扫描线求轮廓周长）

题目链接：http://poj.org/problem?id=1177

题目大意：若干个矩形，求这些矩形重叠形成的图形的轮廓周长。

解题思路：这里引用一下大牛的思路：kuangbin

总体思路:

1.沿X轴离散化建树

2.按Y值从小到大排序平行与X轴的边,然后顺序处理

如果遇到矩形下面那条边则插入到线段树中,遇到矩形上面的边则将相应的边删除掉

根据线段树当前的状态统计长度

第二点是本题的核心思想,偶再举个例:

第一次求出的部分很好理解.

第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的长度,将这个值再减去上次的就少了中间那部分

第三次因为是矩形的上边,所以要删除在那条长的线段.此时的线段树返回的则是第一次的长度,将此值减去第二次返回值,再取其负值就是红色X轴那部分了

最后那条X轴的,再补上就行了。

我写的稍微有点不同，不过大概也就是这个思路了。总结一下就是矩形下位边cnt+1,上位边cnt-1，求tree[1].sum，这些步骤跟求矩形面积并是一样的。

然后按照扫描线从小到大一次跟新，ans+=abs（上一次的测度-更新后的测度）。

然后就按x,y方向扫描线各求一遍，加在一起就是总的周长。（好像还是有点问题，就是重边会出错，不会改啊！！！算了，等以后变强了再来改0 0）

这题我没有离散化，因为数据不是很大也没有小数所以就懒得写了。。。

代码：

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define LC(a) (a<<1)

 #define RC(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 using namespace std;

 typedef long long LL;

 const int INF=0x3f3f3f3f;

 const int N=1e4+;

 struct Node{

     int l,r,cnt,sum;//sum为测度

 }tree[N**]; 

 struct node{

     int l,r,h,flag;

     node(){}

     node(double a,double b,double c,double d){

         l=a;r=b;h=c;flag=d;

     }

 }a[N],b[N];

 bool cmp(node a,node b){

     return a.h<b.h;

 }

 //因为每条线段对应删除的线段是严格出现的，不需要Lazy也就不需要pushdown（）

 void pushup(int p) {

     if(tree[p].cnt>)

         tree[p].sum=tree[p].r-tree[p].l+;

     else if(tree[p].l==tree[p].r)

         tree[p].sum=;

     else

         tree[p].sum=tree[LC(p)].sum+tree[RC(p)].sum;

 }

 void build(int p,int l,int r){

     tree[p].l=l;

     tree[p].r=r;

     if(l==r){

         tree[p].cnt=tree[p].sum=;

         return;

     }

     build(LC(p),l,MID(l,r));

     build(RC(p),MID(l,r)+,r);

     pushup(p);

 }

 void update(int p,int l,int r,int cnt){

     if(l>tree[p].r||r<tree[p].l)

         return;

     if(l<=tree[p].l&&r>=tree[p].r&&tree[p].cnt!=-){

         tree[p].cnt+=cnt;

         pushup(p);

         return;

     }

     update(LC(p),l,r,cnt);

     update(RC(p),l,r,cnt);

     pushup(p);

 }

 int main(){

     int n;

     while(~scanf("%d",&n)){

         int m1=,m2=;

         for(int i=;i<=n;i++){

             int x1,x2,y1,y2;

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

             x1+=N,x2+=N,y1+=N,y2+=N;//防止x,y出现负数

             a[++m1]=node(x1,x2,y1,);

             b[m1]=node(y1,y2,x1,);

             a[++m1]=node(x1,x2,y2,-);

             b[m1]=node(y1,y2,x2,-);

         }

         sort(a+,a++m1,cmp);

         sort(b+,b++m1,cmp);

         //自下往上扫描一遍

         build(,,*N-);

         int ans=;

         for(int i=;i<=m1;i++){

             int last=tree[].sum;

             int l=a[i].l;

             int r=a[i].r-;

             update(,l,r,a[i].flag);

             ans+=abs(tree[].sum-last);

         }

         //自左往右扫描一遍

         build(,,*N-);

         for(int i=;i<=m1;i++){

             int last=tree[].sum;

             int l=b[i].l;

             int r=b[i].r-;

             update(,l,r,b[i].flag);

             ans+=abs(tree[].sum-last);

         }

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

     }

     return ;

 }

巴特西

POJ 1177 Picture（线段树：扫描线求轮廓周长）

最新文章

热门文章