[TIOJ 1202] 重疊的天際線

作法：

把每個房子的左端點和右端點各看成一個事件，一個是有一個高 h 的東西進來，一個是出去，所以就可以用 multiset 維護高度們形成的集合，而裡面的最大值就是當前的高度，只要當當前高度和上一個不一樣的時候就馬上 print 就OK了。

code :

#include<bits/stdc++.h>
using namespace std;
 
struct P
{
    int pos,h,type;
    bool operator < (const P &rhs) const
    {
        if(pos!=rhs.pos) return pos<rhs.pos ;
        if(h!=rhs.h) return h<rhs.h ;
        return type<rhs.type ;
    }
};
 
multiset<int,greater<int> > s ;
vector<P> v ;
main()
{
    int n ;
    while(scanf("%d",&n)==1 && n)
    {
        s.clear() ;
        v.clear() ;
        while(n--)
        {
            int l,h,r ; scanf("%d%d%d",&l,&h,&r) ;
            v.push_back((P){l,h,1}) ;
            v.push_back((P){r,h,2}) ;
        }
        sort(v.begin(),v.end()) ;
        int now=0 ;
        s.insert(0) ;
        for(int i=0;i<v.size();)
        {
            int i2=i ;
            while(i2<v.size() && v[i2].pos==v[i].pos)
            {
                if(v[i2].type==1) s.insert(v[i2].h) ;
                else s.erase(s.find(v[i2].h)) ;
                i2++ ;
            }
            if(*s.begin() != now) { now=*s.begin() ; printf("%d %d ",v[i].pos,now) ; }
            i=i2 ;
        }
        printf("\n") ;
    }
}