合工大 程序设计与艺术 实验三.doc

.程序设计艺术与方法课程实验报告实验名称实验三 计算几何算法的实现姓 名系院专业班 级学 号实验日期6.5指导教师徐本柱成 绩一、实验目的和要求(1) 理解线段的性质、叉积和有向面积。(2) 掌握寻找凸包的算法。 (3) 综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容1掌握线段的性质以及叉积和有向面积的计算方法。2预习寻找凸包的算法。三、实验项目摘要(1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。(2) 完成讲义第三章的课后习题，上机运行并检验结果。(3) 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。(4) 房间最短路问题：给定一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在 x=0,x=10,y=0 和 y=10。起点和终点固定在(0,5)和(10,5)。房间里还有 0 到 18 个墙，每个墙有两个门。输入