洛谷 P1382

#include <bits/stdc++.h>
using namespace std;
int n,cnt,num   ;
struct build
{
    int h,l,r;
}a[100010]; //楼房
struct line
{
    int up,x,k; //up代表线高度(楼房左右边线),k代表出入属性,1代表入，2代表出
}l[200020];
struct ANS
{
    int ax,ay;
}ans[400040]; //储存答案的交叉点
int cmp(line a,line b)
{
    if(a.x != b.x) return a.x<b.x;
    if(a.k != b.k) return a.k<b.k;//入度优先
    // 区分入度出度考虑高度优先级
    if(a.k == 1) return a.up > b.up; //入度，高的优先
    if(a.k == 2) return a.up < b.up; //出度，矮的优先
}
multiset<int> s;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].h >> a[i].l >> a[i].r;
        l[++cnt] = {a[i].h,a[i].l,1}; //楼左，入度
        l[++cnt] = {a[i].h,a[i].r,2}; //楼右，出度
    }
    s.insert(0); //初始化最高为0
    sort(l+1,l+cnt+1,cmp);

    for(int i=1;i<=cnt;i++)
    {
        int m = *s.rbegin(); //存最大高度
        if(l[i].k==1)
        {
            if(l[i].up <= m) s.insert(l[i].up);
            else
            {
                ++num;ans[num].ax=l[i].x;ans[num].ay=m;
                ++num;ans[num].ax=l[i].x;ans[num].ay=l[i].up;
                s.insert(l[i].up);
            }
        }
        else if(l[i].k == 2)
        {
            if(l[i].up==m && s.count(m)==1)
            {
                s.erase(m); //移除该高度(存交叉点)，继续下
                ++num;ans[num].ax=l[i].x;ans[num].ay=l[i].up;
                ++num;ans[num].ax=l[i].x;ans[num].ay=*s.rbegin();
            }
            else s.erase(s.find(l[i].up));
        }
    }
    cout << num << '\n';
    for(int i=1;i<=num;i++) cout << ans[i].ax << ' ' << ans[i].ay << '\n';
    return 0;
}