《程序设计艺术与方法》课程实验报告实验名称姓名实验日期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 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的 x 位置和两个门的 y 坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析（源程序及相关说明）思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。用跨立的方法。线段相交满足且只需满足如下两个条件就可以了：（1）两条线段相互跨立；（2）一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方，若p1p2 跨立 p3p4，则（p1-p3）×(p4-p3)*（p2-p3）×(p4-p3)>0，当（p1-p3）×(p4-p3)=0 时，说明 p1,p3,p4 共线，但是因为已经通过了快速排斥实验，所以点 p1 一定在线段 p3,p4 上。所以判断线段 p1p2,p3p4 相交的依据是（p1-p3）×(p4-p3)*（p2-p3）×(p4-p3)>=0。#include
#include using namespace std;typedef pair POINT;double direction(POINT p,POINT p1,POINT p2){POINT v1,v2;v1.first =p2.first -p.first ;v1.second=p2.second-p.second;v2.first =p1.first -p.first;v2.second=p1.second-p.second;return v1.first*v2.second-v1.second*v2.first;}bool on_segment(POINT p,POINT p1,POINT p2){double min_x=p1.firstp2.first?p1.first:p2.first;double min_y=p1.secondp2.second?p1.s...
