凸包入门之卷包裹法 & hdu 1348 wall

凸包入门之卷包裹法 & hdu 1348 wall

在二维空间中，凸包可以简单的认为是最小的包含所有点的凸多边形。

简单的卷包裹法：寻找最边缘（最下方的，次之是最左边的；或者最左边的，次之最下边）点。假想用一根绳子向右逆时针旋转碰到另一个点，这样新找到的点作为端点，继续旋转绳子重复找点的步骤，一直围成一个凸多边形。时间复杂度：O(n^2)     //我把此代码和Graham-scan比较了一下，没有理解为什么他就是 O(n^2) T_T

(如果在寻找的射线上有多个点的情况，使用和保留离前端点最远的那一点）

因为涉及到旋转和夹角，所以运用到了叉积。

例子：

hdu 1348  wall

​​#include #include #include using namespace std;struct point{ int x,y;}pt[1005];int sta[1005],ans[1005],cnt;int cmp(point a,point b){ //左下角优先 先左再下 return a.x1&&cross(pt[sta[top-2]],pt[sta[top-1]],pt[i])<=0) { top--; } sta[top++]=i; } for(int i=0;i=0;i--){ while(top>1&&cross(pt[sta[top-2]],pt[sta[top-1]],pt[i])<=0){ top--; } sta[top++]=i; } for(int i=0;i>t; while(t--){ scanf("%d%d",&n,&l); for(int i=0;i

再来模仿一种写法：

#include #include #include #include using namespace std;struct point{ int x,y;}pt[1005],ans[1005];int cnt;int cmp(point a,point b){ if(a.x==b.x) return a.y1&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0) { cnt--; } ans[cnt++]=pt[i]; } int key=cnt; //求上凸包 (将pt[n-1]和pt[0]连接起来。) for(int i=n-2;i>=0;i--){ while(cnt>key&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0){ cnt--; } ans[cnt++]=pt[i]; }}int main(){ //freopen("cin.txt","r",stdin); int n,l; double Pi=atan(1.0)*4; int t=0; cin>>t; while(t--){ scanf("%d%d",&n,&l); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。