题解 P1382 【楼房】

shuri001 · 2017-10-22 20:56:37 · 题解

扫描线

注释非常详细 请看看ovo

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int n,cnt,num;
struct build{
    int h,l,r;//高，左，右 
}a[100010];
struct line{
    int up,x,k;//高，x轴，出入属性 
}l[200020];//扫描线 
struct ANS{
    int ax,ay;//左边，右边 
}ans[400040];
int read(){
    char c=getchar();int num=0,flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return num*flag;

}//读入优化

multiset<int>s;//存高度，默认递增，可以重复 
int cmp(line i,line j){
    if(i.x!=j.x)return i.x<j.x;//如果靠左的排到前面 
    if(i.k!=j.k)return i.k<j.k;//入边在前 
    if(i.k==1)return i.up>j.up;//入边越高越容易挡住 
    if(i.k==2)return i.up<j.up;//出边越矮越容易挡住 
}
int main(){
    n=read();//读边数 
    for(int i=1;i<=n;i++){
        a[i].h=read(),a[i].l=read(),a[i].r=read();//读入 
        l[++cnt].up=a[i].h,l[cnt].x=a[i].l,l[cnt].k=1;//加入边 
        l[++cnt].up=a[i].h,l[cnt].x=a[i].r,l[cnt].k=2;//加出边 
    }
    sort(l+1,l+cnt+1,cmp);//为扫描排序 
    s.insert(0);//初始最大高度为0 
    for(int i=1;i<=cnt;i++){
        int mx=*s.rbegin();//取最高的高度 
        if(l[i].k==1){//如果是入边 
            if(l[i].up<=mx) s.insert(l[i].up);//比最高矮，加入堆 
            else{
                ++num;ans[num].ax=l[i].x;ans[num].ay=mx;//记录交叉点 
                ++num;ans[num].ax=l[i].x;ans[num].ay=l[i].up;//记录交叉点上面的点 
                s.insert(l[i].up);//加高 
            }
        }
        if(l[i].k==2){//如果是出边 
            if(l[i].up==mx&&s.count(mx)==1){//如果当前的就是最高的线，而且，没有跟它一样高的 
                s.erase(mx);//取出这一条 
                ans[++num].ax=l[i].x; ans[num].ay=l[i].up;// 记录右上顶点 
                ans[++num].ax=l[i].x;ans[num].ay=*s.rbegin();//记录交叉点 
            }
            else s.erase(s.find(l[i].up));//删掉一样高的边 
        }
    }
    printf("%d\n",num);//输出节点个数 
    for(int i=1;i<=num;i++)   printf("%d %d\n",ans[i].ax,ans[i].ay); //输出结果 
    return 0;
}