数据结构与算法实验题 条形图轮廓问题
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/08/19 13:46:16
数据结构与算法实验题 条形图轮廓问题
★实验任务
在x 轴上水平放置着n 个条形图.条形图的轮廓是消去这n 个条形图的隐藏线后得到的
图形,如图所示.![](http://img.wesiedu.com/upload/1/0d/10d5d09808939330fe8b0194712cca36.jpg)
每个条形图由3 元组(Li,Hi,Ri)表示.其中,Li 和Ri 分别为条形图左右竖线的x
坐标值,Hi 为条形图的高度.例如,上图的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).条形图的轮廓可用轮廓向
量(V1,V2,…,Vm)表示.当i 为奇数时,Vi 表示条形图轮廓中一条竖线的x 坐标值:当
i 为偶数时,Vi 表示条形图轮廓中一条横线的高度.例如,上图的条形图轮廓向量为
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0).
现在,对于给点的n 个条形图,计算其条形图轮廓.
★数据输入
第一行一个正整数n,表示n 个条形图(1 <= n <= 4000).
接下来n 行,每行有3 个整数(Li,Hi,Ri),Li 和Ri 分别为条形图左右竖线的x 坐标
值,Hi 为条形图的高度(-3000 <= Li,Ri<= 3000, 1 <= Hi <= 1000).
★数据输出
输出计算出的条形图轮廓向量.
输入示例输出示例
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
★实验任务
在x 轴上水平放置着n 个条形图.条形图的轮廓是消去这n 个条形图的隐藏线后得到的
图形,如图所示.
![](http://img.wesiedu.com/upload/1/0d/10d5d09808939330fe8b0194712cca36.jpg)
每个条形图由3 元组(Li,Hi,Ri)表示.其中,Li 和Ri 分别为条形图左右竖线的x
坐标值,Hi 为条形图的高度.例如,上图的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).条形图的轮廓可用轮廓向
量(V1,V2,…,Vm)表示.当i 为奇数时,Vi 表示条形图轮廓中一条竖线的x 坐标值:当
i 为偶数时,Vi 表示条形图轮廓中一条横线的高度.例如,上图的条形图轮廓向量为
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0).
现在,对于给点的n 个条形图,计算其条形图轮廓.
★数据输入
第一行一个正整数n,表示n 个条形图(1 <= n <= 4000).
接下来n 行,每行有3 个整数(Li,Hi,Ri),Li 和Ri 分别为条形图左右竖线的x 坐标
值,Hi 为条形图的高度(-3000 <= Li,Ri<= 3000, 1 <= Hi <= 1000).
★数据输出
输出计算出的条形图轮廓向量.
输入示例输出示例
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
![数据结构与算法实验题 条形图轮廓问题](/uploads/image/z/5925713-41-3.jpg?t=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%AE%9E%E9%AA%8C%E9%A2%98+%E6%9D%A1%E5%BD%A2%E5%9B%BE%E8%BD%AE%E5%BB%93%E9%97%AE%E9%A2%98)
#include
#include
#include
#define LBound (-3000)
#define UBound 3000
#define Cod2Idx(x) ((x)-LBound)
#define Size Cod2Idx(UBound+1)
int main() {
int hs[Size],n;
int i,l,r,h,i0,i1;
memset(hs,0,sizeof(*hs) * Size);
scanf("%d",&n);
for (i0=UBound,i1=LBound; n>0; n--) {
scanf("%d %d %d",&l,&h,&r);
if (l < i0) i0 = l;
if (r > i1) i1 = r;
for (i=l; i
#include
#include
#define LBound (-3000)
#define UBound 3000
#define Cod2Idx(x) ((x)-LBound)
#define Size Cod2Idx(UBound+1)
int main() {
int hs[Size],n;
int i,l,r,h,i0,i1;
memset(hs,0,sizeof(*hs) * Size);
scanf("%d",&n);
for (i0=UBound,i1=LBound; n>0; n--) {
scanf("%d %d %d",&l,&h,&r);
if (l < i0) i0 = l;
if (r > i1) i1 = r;
for (i=l; i