2995 楼房
时间限制: 1 s
空间限制: 256000 KB
题目等级 :
黄金 Gold
题目描述 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]
/*
by ylf%%%%%%%%%%%.
set.
依照题目设置的顺序构造cmp.
维护当前hmax.
为了避免重复覆盖的情况,左端点从大到小排序.
还有右端点要从小到大排序,不然就会多记录一些点.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#define MAXN 2000001
using namespace std;
multiset<int,greater<int> >s;
struct data{int x,y,k,h;}ss[MAXN];
int n,m,cut,tot,ans,a[MAXN],b[MAXN];
bool cmp(const data &x,const data &y)
{
if(x.x!=y.x) return x.x<y.x;
if(x.k!=y.k) return x.k<y.k;
if(x.k==1) return x.h>y.h;
if(x.k==2) return x.h<y.h;
}
void slove()
{
for(int i=1;i<=2*n;i++)
{
if(ss[i].k==1)
{
if(*s.begin()>=ss[i].h) s.insert(ss[i].h);
else{
a[++tot]=ss[i].x,b[tot]=*s.begin();
a[++tot]=ss[i].x,b[tot]=ss[i].h;
s.insert(ss[i].h);
}
}
else
{
if(*s.begin()==ss[i].h&&s.count(ss[i].h)==1)
{
s.erase(s.find(ss[i].h));
a[++tot]=ss[i].x,b[tot]=ss[i].h;
a[++tot]=ss[i].x,b[tot]=*s.begin();
}
else s.erase(s.find(ss[i].h));
}
}
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
printf("%d %d\n",a[i],b[i]);
}
int main()
{
int x,y,h;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&h,&x,&y);
ss[++cut].k=1,ss[cut].x=x,ss[cut].h=h;
ss[++cut].k=2,ss[cut].x=y,ss[cut].h=h;
}
sort(ss+1,ss+cut+1,cmp);
slove();
return 0;
}**