首页 > 代码库 > codevs 2995 楼房

codevs 2995 楼房

题目描述 Description

地平线(x轴)上有n个矩(lou)形(fang),用三个整数h[i],l[i],r[i]来表示第i个矩形:矩形左下角为(l[i],0),右上角为(r[i],h[i])。地平线高度为0。在轮廓线长度最小的前提下,从左到右输出轮廓线。

技术分享
输入描述 Input Description

第一行一个整数n,表示矩形个数

以下n行,每行3个整数h[i],l[i],r[i]表示第i个矩形。

输出描述 Output Description

第一行一个整数m,表示节点个数

以下m行,每行一个坐标表示轮廓线上的节点。从左到右遍历轮廓线并顺序输出节点。第一个和最后一个节点的y坐标必然为0。

样例输入 Sample Input

【样例输入】

2
3 0 2
4 1 3

【样例输入2】

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

样例输出 Sample Output

【样例输出】

6
0 0
0 3
1 3
1 4
3 4
3 0

【样例输出2】

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

数据范围及提示 Data Size & Hint

对于30%的数据,n<=100

对于另外30%的数据,n<=100000,1<=h[i],l[i],r[i]<=1000

对于100%的数据,1<=n<=100000,1<=h[i]<=10^9,-10^9<=l[i]<r[i]<=10^9

 

先把数据横坐标离散化

线段树维护每一列的高度最大值

注意 楼房区间[l,r],线段树更改的区间为[l,r-1]

发现对于每一列,先输出(x,上一条边的y),再输出(x,这一条边的y)

#include<algorithm>#include<cstdio>#include<queue>#define N 100001using namespace std;int xi[N],yi[N],h[N],hash[2*N],cnt;int n,maxn[N*8],opl,opr,w,ans;int f[N*8],out1[N*4],out2[N*4],tot;struct TREE{    void down(int k)    {        maxn[k<<1]=max(maxn[k<<1],f[k]);        maxn[k<<1|1]=max(maxn[k<<1|1],f[k]);        f[k<<1]=max(f[k<<1],f[k]);        f[k<<1|1]=max(f[k<<1|1],f[k]);        f[k]=0;    }    void solve(int k,int l,int r,int p)    {        if(l>=opl&&r<=opr)        {            if(p==1)            {                maxn[k]=max(maxn[k],w);                f[k]=max(f[k],w);                }            else ans=maxn[k];            return ;        }        if(f[k]) down(k);        int mid=l+r>>1;        if(opl<=mid) solve(k<<1,l,mid,p);        if(opr>mid) solve(k<<1|1,mid+1,r,p);        if(p==1) maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);    }}tr;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d",&h[i]);        scanf("%d%d",&xi[i],&yi[i]);        hash[i*2-1]=xi[i]; hash[i*2]=yi[i];    }    sort(hash+1,hash+2*n+1);    cnt=unique(hash+1,hash+2*n+1)-(hash+1);    for(int i=1;i<=n;i++)    {        opl=lower_bound(hash+1,hash+cnt+1,xi[i])-hash;        opr=lower_bound(hash+1,hash+cnt+1,yi[i])-hash-1;        w=h[i];        tr.solve(1,1,cnt,1);    }    int last=0;    for(int i=1;i<=cnt;i++)    {        opl=opr=i;        tr.solve(1,1,cnt,2);        if(ans!=last)        {            out1[++tot]=hash[i]; out2[tot]=last;            out1[++tot]=hash[i]; out2[tot]=ans;            last=ans;        }    }    printf("%d\n",tot);    for(int i=1;i<=tot;i++) printf("%d %d\n",out1[i],out2[i]);}

 

codevs 2995 楼房