计算机辅助设计

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte

描述

 

在计算机辅助设计(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）

 

输入

 

输入的第一行为一个整数N，表示建筑物的数目，接下来的N行的输入中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于 1000。建筑物的数目不会超过 50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。

 

输出

 

输出中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表轮廓线顶点的水平坐标，如上面的图例所示。

 

样例输入

8

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

 

题解一：刚开始把问题想得特复杂，不断的拿两个区间比，重叠部分不好判断，最后在CDD同学的帮助下想到可以根据高度来更新点。

     先把每段区间[x,h,y]的高度赋为h，如果右面的区间[x1,h1,y1]中，x1>x&&y1<y，取重叠部分[x1,y]的最大高度

max = h>h1?h:h1.

     具体过程可看代码......

 

 

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;struct Node{    int x,h,y;};Node p[52];int main(){    int n,i,j,Max;    int high[1010];    while(~scanf("%d",&n))    {        memset(high,0,sizeof(high));        Max=0;        for(i=0;i
            
           
          
         
        

题解二：两层循环枚举

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;struct node{ int x; int y; int h;}p[1010];int main(){ int n,i,j,k; int a,b,pp,qq; vector
              
                q; while(~scanf("%d",&n)) { b = 0,a = 0xfffffff; for(i=0;i
               
                b) b = p[i].y; } qq = 0; for(i=a;i<=b;i++) { pp = 0; for(j=0;j
                
                 =p[j].x && i
                 
                   pp) pp = p[j].h; } } if(pp!=qq) { node v; v.x = i; v.y = pp; q.push_back(v); qq = pp; } } for(i=0;i