首页 > 代码库 > POJ 1177/HDU 1828 picture 线段树+离散化+扫描线 轮廓周长计算

POJ 1177/HDU 1828 picture 线段树+离散化+扫描线 轮廓周长计算

2024-07-14 10:13:53   219人阅读

求n个图矩形放下来，有的重合有些重合一部分有些没重合，求最后总的不规则图型的轮廓长度。

我的做法是对x进行一遍扫描线，再对y做一遍同样的扫描线，相加即可。因为最后的轮廓必定是由不重合的线段长度组成的，这样理论上是对的

要注意处理高度相同的线段，把底边优先处理（在代码里就是f标记为1的线段），因为若是一个矩形的底边和另一个矩形的上边重合，则这个轮廓肯定不能算

不过POJ和HDU的数据好像都比较弱，我没进行上面的细节处理也AC了，不过一个很简单的数据就会不对，所以还是要处理一下才是真正正确的代码

我之前敲代码的时候还想起在线段树里面的覆盖要涉及懒惰标记（因为是对区间进行覆盖嘛，没向子走）和向上更新。。。不过想了一下不用，这个线段树不是普通那种，因为总是先覆盖底边，然后由等长的上边来解除覆盖，所以区间总是相对不变的，没必要进行向上或者向下更新

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define lson rt<<1,l,mid#define rson rt<<1|1,mid,rusing namespace std;const int N=10010;struct node{    int lx,ly,hx,hy;}rec[N];struct node2{    int l,r,h,f;    bool operator <(const node2& rhs) const{        if (h==rhs.h){            return f>rhs.f;        }        else return h<rhs.h;    }}seg[N*2];int X[N*2];int n;int flag[N<<2];int d[N<<2];void build(int rt,int l,int r){    flag[rt]=0;    d[rt]=0;    if (r-l<=1) return;    int mid=(l+r)>>1;    build(lson);    build(rson);}void up(int rt,int l,int r){    if (flag[rt]>0){        d[rt]=X[r]-X[l];    }    else    {        if (r-l<=1) d[rt]=0;        else d[rt]=d[rt<<1]+d[rt<<1|1];    }}void cover(int L,int R,int v,int rt,int l,int r){    if (L<=l && r<=R)    {        flag[rt]+=v;        up(rt,l,r);        return;    }    if (r-l<=1) return ;    int mid=(l+r)>>1;    if (R<=mid) cover(L,R,v,lson);    else    if (L>mid)  cover(L,R,v,rson);    else    {        cover(L,R,v,lson);        cover(L,R,v,rson);    }    up(rt,l,r);}int main(){    while (scanf("%d",&n)!=EOF)    {        int cnt=0;        for (int i=0;i<n;i++){            scanf("%d%d%d%d",&rec[i].lx,&rec[i].ly,&rec[i].hx,&rec[i].hy);            X[++cnt]=rec[i].lx;            seg[cnt].l=rec[i].lx;            seg[cnt].r=rec[i].hx;            seg[cnt].h=rec[i].ly;            seg[cnt].f=1;            X[++cnt]=rec[i].hx;            seg[cnt].l=rec[i].lx;            seg[cnt].r=rec[i].hx;            seg[cnt].h=rec[i].hy;            seg[cnt].f=-1;        }        int m=1;        sort(X+1,X+1+cnt);        sort(seg+1,seg+1+cnt);        for(int i=2;i<=cnt;i++){            if (X[i]!=X[i-1]){                X[++m]=X[i];            }        }        int ans=0;        build(1,1,m);        //for (int i=1;i<=m;i++) cout<<X[i]<<endl;        for (int i=1;i<=cnt;i++){            //cout<<seg[i].l<<" "<<seg[i].r<<" "<<seg[i].f<<endl;            int l=lower_bound(X+1,X+1+m,seg[i].l)-X;            int r=lower_bound(X+1,X+1+m,seg[i].r)-X;            int tmp=d[1];            //cout<<X[l]<<" xxx "<<X[r]<<endl;           // cout<<"bf: "<<d[1]<<endl;            cover(l,r,seg[i].f,1,1,m);            tmp=d[1]-tmp;            if (tmp<0) tmp=-tmp;            //cout<<"af: "<<d[1]<<endl;            //cout<<tmp<<endl;            ans+=tmp;        }        //cout<<ans<<endl;        cnt=0;        for (int i=0;i<n;i++){            X[++cnt]=rec[i].ly;            seg[cnt].l=rec[i].ly;            seg[cnt].r=rec[i].hy;            seg[cnt].h=rec[i].lx;            seg[cnt].f=1;            X[++cnt]=rec[i].hy;            seg[cnt].l=rec[i].ly;            seg[cnt].r=rec[i].hy;            seg[cnt].h=rec[i].hx;            seg[cnt].f=-1;        }        sort(X+1,X+1+cnt);        sort(seg+1,seg+1+cnt);        m=1;        for (int i=2;i<=cnt;i++){            if (X[i]!=X[i-1]){                X[++m]=X[i];            }        }        build(1,1,m);        for (int i=1;i<=cnt;i++){            int l=lower_bound(X+1,X+1+m,seg[i].l)-X;            int r=lower_bound(X+1,X+1+m,seg[i].r)-X;            int tmp=d[1];            cover(l,r,seg[i].f,1,1,m);            tmp=d[1]-tmp;            if (tmp<0) tmp=-tmp;            ans+=tmp;        }        printf("%d\n",ans);    }    return 0;}/*20 0 5 22 -2 4 3*/

　　


联系
我们