【题目来源】
湖南省首届“湘邮科技杯”大学生程序设计大赛，数据范围有改动
【题目描述】
在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段）。你需要设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的，而且全部建立在同一水平面上。每个建筑物用一个三元组表示(Li,Hi,Ri)其中Li和Ri分别是建筑物i 的左右边缘坐标，Hi是建筑物i的高度。
下面左图中的建筑物分别用如下三元组表示：
(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)
下面右图中的城市侧视轮廓线用如下的序列表示：
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)
【输入格式】
输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于109。建筑物的数目不会超过10000。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照Li排序，即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。
【输出格式】
输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表轮廓线顶点的水平坐标，如上面的图例所示。
【输入样例】
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
【输出样例】
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
【题目分析】
本题其实是矩形覆盖问题的特殊情形——固定了矩形的下边界。本题可以使用矩形切割或者离散化加上线段树解决，但是前者的时间复杂度在最坏情况下可能达到O(n3)，而后者的编程实现比较复杂。
本文将介绍一种时间复杂度稳定在O(nlogn)，且编程比较简单的分治算法。
这种算法的思路是：要求n个矩形的轮廓，先将这n个矩形分成两个大小相等的部分，分别求其轮廓，然后再将这两个轮廓合并。
规模为1的问题可以直接解决。具体来说，如果这个矩形的三元组表示为(L,H,R)，那么其轮廓为(L,H,R,0)。
对于规模为k的问题，假设得到了两个规模为k/2的轮廓，分别为A和B，我们如何得到合并后的轮廓C？首先，容易证明轮廓C的每一个横坐标，都来源于轮廓A和B的横坐标，而不会产生新的坐标值。因此，我们只需计算A和B中所有涉及到的横坐标在C中的高度。由于轮廓C中的横坐标值要求有序，我们可以仿照归并排序的方法，用两个指针扫描轮廓A和B。具体的方法是，设指针i指向轮廓A的当前横坐标，指针j指向轮廓B的当前横坐标。如果指针i指向的横坐标较小，那么将这一横坐标加入到C中，且在C中的高度为A中第i个横坐标对应的高度与B中第j-1个横坐标对应的高度的最大值，然后将指针i向后移一位；指针j指向的横坐标较小的情况则类似处理。如果两个指针指向的横坐标相同，此时只需将这一横坐标加入到C中一次，且高度为两指针指向高度的最大值，然后将两指针同时向后移一位。最后，需要扫描一遍轮廓C，将相邻的高度相同的横坐标合并。
分析时间复杂度，设T(n)表示解决规模为n的问题需要的时间，那么有。解此递归方程，得到T(n)=O(nlogn)。空间方面，由于递归的层数为O(logn)，每一层需要保存O(n)的空间，所以总的空间复杂度为O(nlogn)。
【性能分析】
时间复杂度：O(nlogn)
空间复杂度：O(nlogn)
编程复杂度：低
【总结】
本题可以采用多种方法解决，本文介绍的分治方法的优势在于：编程简单、时间复杂度低。
【代码】//代码原创
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Node{
int l,h;
Node(int x=0,int y=0):l(x),h(y){}
};
int n,l;
vector<Node>s[10010];
Node s2[10010];
inline int Max(int x,int y){return x>y?x:y;}
void merge(int l,int r,int h){
if(l==r)return;
int mid=(l+r)/2,i=0,j=0,k=0;
merge(l,mid,1);merge(mid+1,r,0);
while(i<s[mid+1].size()&&j<s[mid].size()){
if(s[mid+1][i].l>s[mid][j].l){
s2[++k].l=s[mid][j].l;
if(i==0)s2[k].h=s[mid][j].h;
else s2[k].h=Max(s[mid][j].h,s[mid+1][i-1].h);
j++;
}
else if(s[mid+1][i].l==s[mid][j].l){
s2[++k].l=s[mid][j].l;
s2[k].h=Max(s[mid][j].h,s[mid+1][i].h);
i++;j++;
}
else{
s2[++k].l=s[mid+1][i].l;
if(0==j)s2[k].h=s[mid+1][i].h;
else s2[k].h=Max(s[mid][j-1].h,s[mid+1][i].h);
i++;
}
}
while(i<s[mid+1].size()){
s2[++k].l=s[mid+1][i].l;
s2[k].h=s[mid+1][i].h;
i++;
}
while(j<s[mid].size()){
s2[++k].l=s[mid][j].l;
s2[k].h=s[mid][j].h;
j++;
}
if(h==0){
s[l].clear();
for(int ls=1;ls<=k;ls++)
if(s2[ls-1].h!=s2[ls].h)
s[l].push_back(s2[ls]);
}
else{
s[r].clear();
for(int ls=1;ls<=k;ls++)
if(s2[ls-1].h!=s2[ls].h)
s[r].push_back(s2[ls]);
}
}
int main(){
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
int x,y,z;
while(scanf("%d%d%d",&x,&y,&z)!=EOF){
s[++n].push_back(Node(x,y));
s[n].push_back(Node(z,y));
}
for(int i=1;i<=n;i++)s[i].push_back(Node(s[i][s[i].size()-1].l,0));
merge(1,n,0);
printf("%d %d",s[1][0].l,s[1][0].h);
for(int i=1;i<s[1].size();i++)
printf(" %d %d",s[1][i].l,s[1][i].h);
return 0;
}