凸包 | 学步园

现在的位置: 首页 > 综合 > 正文

凸包

2014年09月05日 ⁄ 综合 ⁄ 共 3351字 ⁄ 字号小中大 ⁄ 评论关闭

凸包的概念：

　　点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

凸包的求法：

　　现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话，Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh)，在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham 扫描法，其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。

　　对于一个有三个或以上点的点集Q，Graham扫描法的过程如下：

令p0为Q中Y-X坐标排序下最小的点
　　设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最远的点外全部移除
　　压p0进栈S
　　压p1进栈S
　　压p2进栈S
for i ← 3 to m
do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
对S弹栈
压pi进栈S
return S;

　　此过程执行后，栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是，我们对点按极角逆时针排序时，并不需要真正求出极角，只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。

hdu 1392 Surround the Trees

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=1392

#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; struct po { int x,y; }f[111]; //表示叉乘 int xc(int x1,int y1,int x2,int y2) { return x1*y2 - y1*x2; } //按与原点的夹角大小排序 //就是看叉乘是左拐还是右拐(正的还是负的) bool cmp(const po &a,const po &b) { return a.x*b.y-a.y*b.x>0; } int main() { int n; int i,j; int xx,yy; double sum; while(scanf("%d",&n),n) { sum=0; int u=1; //u来记录最下面,且最左边的点的位置 for(i=1;i<=n;i++) { scanf("%d%d",&f[i].x,&f[i].y); if(f[u].y>f[i].y||(f[u].y==f[i].y&&f[u].x>f[i].x)) u=i; } if(n==1) { printf("%.2lf/n",sum); continue; } else if(n==2) { sum=sqrt(( f[2].x-f[1].x+0.0 ) * ( f[2].x-f[1].x+0.0 ) + ( f[2].y-f[1].y+0.0 ) * ( f[2].y-f[1].y+0.0 ) ); printf("%.2lf/n",sum); continue; } //把最下面最左边的点换到第一个位置,( 为了下面的排序 ) xx=f[u].x,yy=f[u].y; f[u].x=f[1].x,f[u].y=f[1].y; f[1].x=xx,f[1].y=yy; //就好比物理有相对位置一样, //这里是把 1 看做的原点, 后面的点和第一个点的相对坐标 for(i=2;i<=n;i++) { f[i].x-=f[1].x; f[i].y-=f[1].y; } f[1].x=0; f[1].y=0; //排序只要从第二个开始就可以了 sort(f+2,f+1+n,cmp); //ans[]数组来记录凸包上的点 int ans[111],top=0; ans[++top]=1; ans[++top]=2; //凸包核心代码 for(i=3;i<=n;i++) { while(1) { int x1=f[ans[top-1]].x,y1=f[ans[top-1]].y; int x2=f[ans[top]].x,y2=f[ans[top]].y; if(xc(x2-x1,y2-y1,f[i].x-x2,f[i].y-y2)<0) top--; else break; } ans[++top]=i; } //求和 double sum=0; ans[top+1]=ans[1]; for(i=1;i<=top;i++) { int x1=f[ans[i]].x,y1=f[ans[i]].y; int x2=f[ans[i+1]].x,y2=f[ans[i+1]].y; sum+= sqrt( (x1-x2+0.0) * (x1-x2+0.0) + (y1-y2+0.0) * (y1-y2+0.0) ); } printf("%.2lf/n",sum); } }

hdu 1348 Wall

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=1348

#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #define pi acos(-1.0) using namespace std; struct po { int x,y; }f[1111]; //叉乘 inline int xc(int x1,int y1,int x2,int y2) { return x1*y2 - y1*x2; } //排序,按与原点的夹角大小排序, // 夹角相等就看哪个最左最下面 inline bool cmp(const po &a,const po &b) { if(a.x*b.y-a.y*b.x!=0) return a.x*b.y-a.y*b.x>0; return a.x<b.x; } int main() { int r,n; int i,j,t; int xx,yy; double sum; scanf("%d",&t); while(t--) { sum=0; scanf("%d%d",&n,&r); int u=1; //u来记录最下面,最左边的点的位置 for(i=1;i<=n;i++) { scanf("%d%d",&f[i].x,&f[i].y); if(f[u].y>f[i].y||(f[u].y==f[i].y&&f[u].x>f[i].x)) u=i; } //把最下面,最左边的点交换到第一个位置 xx=f[u].x,yy=f[u].y; f[u].x=f[1].x,f[u].y=f[1].y; f[1].x=xx,f[1].y=yy; //改为相对第一个点的相对坐标 //为下面的排序准备 for(i=2;i<=n;i++) { f[i].x-=f[1].x; f[i].y-=f[1].y; } f[1].x=0; f[1].y=0; //第2个点开始就可以了 sort(f+2,f+1+n,cmp); //ans[] 来记录凸包上的点 int ans[1111],top=0; ans[++top]=1; ans[++top]=2; //凸包核心代码 for(i=3;i<=n;i++) { while(1) { int x1=f[ans[top-1]].x,y1=f[ans[top-1]].y; int x2=f[ans[top]].x,y2=f[ans[top]].y; if(xc(x2-x1,y2-y1,f[i].x-x2,f[i].y-y2)<0) top--; else break; } ans[++top]=i; } double sum=0; ans[top+1]=ans[1]; //求和 for(i=1;i<=top;i++) { int x1=f[ans[i]].x,y1=f[ans[i]].y; int x2=f[ans[i+1]].x,y2=f[ans[i+1]].y; sum+= sqrt( (x1-x2+0.0) * (x1-x2+0.0) + (y1-y2+0.0) * (y1-y2+0.0) ); } printf("%d/n",(int)(sum+2.0*pi*(r+0.0)+0.500)); if(t) puts(""); } }

不断更新中……