凸包问题解题报告

《凸包问题解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、凸包问题解题报告题目：在平面上给定了N个点，求包含这N个点的最小凸几何体，如下：算法思路：找出输入节点中的y值最小的点，如果有若干个y值相同的点，选择出x最小的点（标号为min）从min开始，按逆时针方向搜寻下一个点，先寻找右上方的点，要求斜率k>0，且斜率要最小，如果右上方找不到点了，再寻找左上方的点，此时要求斜率k<0，且斜率要最小，如果左上方也找不到点了，继续寻找左下方的点，此时要求斜率k>0，且斜率要最小，如果左下方也找不到满足要求的点了，则最后寻找右下方的点，直到重新找到起始的min点，说明此次搜寻结束。算法思路并不难，下

2、面说一些程序运行时的技巧。1、从上面的思路中可以看到，有四个方向要去寻找，如果分4段写，无疑是比较麻烦的，有没有什么好的办法，可以缩短代码？可以，我们可以考虑用一个循环来一次将四个方向都给搜遍：注意观察一下，假设当前节点的坐标为，而被测试节点的坐标为，考虑到实际运算的情况，则四个方向分别满足如下条件即可：右上方的满足条件是：（在右侧的点的必定大于）左上方的满足条件是：（在上方的点的必定小于）左下方的满足条件是：（在左侧的点的必定小于）右下方的满足条件是：（在下方的点的必定大于）而如果第一个和第二个条件不等式的两边同时乘以1，第三个和

3、第四个条件不等式的两边同时乘以-1，则四个不等式全都是大于的关系。而第一个和第三个比较的是和的关系，第二个和第四个比较的是和的关系，因此对于如下循环For(inti=0;i<4;++i)表示的四个方向循环for(intj=0;jpoint[j][i%2]*pow(-1,i/2)){.......}由此解决了四个方向的循环问题。2、在上述的循环当中，可以用一个变量direction记录当前已经循环到第几个

4、方向了，假设已经循环到了第2个方向，即搜寻左上方的点，那么后续的点，每次搜寻时，都只需要从左上方开始搜索即可，可以节约时间3、需要注意的的一点是：在计算斜率的时候，需要用到浮点数的乘除，而输入的时候都是输入的整形数，因此有如下两种解决方案：①将输入的数都定义成浮点数②定义斜率k为double型数，在计算k时，每个坐标x,y都需要乘以0.1进行计算附代码：（注：下面的代码由于我测试的时候嫌输入比较烦，调用了系统的随机数，即每次只需要输入点的个数n，然后系统会自动生成n个点，然后绘出了这n个点在坐标系中的位置。有些变量名可能和前面解释的

5、不一样）#include#includeusingnamespacestd;intmatrix[100][2];intnum;intline[100];intlocate=0;intdirection[4]={1,1,-1,-1};//{1,-1,1,-1}doublexielv[4]={10000,10000,10000,10000};voidinit();//初始化，输入n，生成n个随即点，并将其在坐标系上标出intgetminy();//寻找最小y值点voidselect();//按上述方法一

6、次搜寻满足条件的点boolexist(intj);//用于select函数，判断第j个点是否已经被选中了boolexist(intx,inty);//用于init函数，用于坐标系上标点，判断输入的点中是否存在(x,y)intmain(){init();select();cout<<"Theresultis:"<

7、<<"pleasetypethenumofpoint:"<>num;inti;for(i=0;i

8、";for(intj=0;j<16;++j){intx=j;inty=15-i;if(exist(x,y)){cout<<".";}else{cout<<"";}}cout<

9、ut<<"

10、";for(i=0;i<15;++i){cout<<"--";}cout<<">"<