什么是凸包？
假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图：
然后，什么是凸包问题？ 我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。 现给出点的数目13，和各个点的坐标。求构成凸包的点？
自己才刚刚接触到这个数学问题。通过几个入门的简单的题，基本上已经有了简单的了解。所以自己先写点东西。为了自己以后
可以好好的复习。
其实凸包就是凸多边形问题。
大佬的博客：凸包五解
点击打开链接
1 凸包问题要求什么？
一般的话来说，入门就是要你找出这个凸多边型，求凸多边的型的面积，周长。其实写到这就可以思考一下，如何求多边。只要
把多边形求出来，那么相对来说就是可以找到周长，面积了。
2: 如何求? 其实大佬的博客中，将这个思想已经完全的讲解出来了。
(1)点的输入
(2)找出很明显的凸包上点的，作为一个开头。
(3)极角排序。
int dis(node c1,node c2) { return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y); } double mutil(node c0,node c1,node c2) { return (c1.x-c0.x)*(c2.y-c0.y)-(c2.x-c0.x)*(c1.y-c0.y); } int cmp(node c1,node c2) { int x=mutil(c1,c2,a[0]); if(x>0||(x==0&&dis(c1,a[0])<dis(c2,a[0]))) return 1; else return 0; }
(4)开始扫描，利用叉乘来判断是不是凸包上的点，将凸包上的点收入到栈堆中（数组也可以）
void Graham() { tot=2; p[0]=a[0],p[1]=a[1]; for(int i=2; i<n; i++) { while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0) tot--; p[tot++]=a[i]; } }
俩个简单的题
NYOJ-78 圈水池 入门凸包输出点
int n,tot; struct node { int x,y; } a[10005],p[10005]; int dis(node c1,node c2) { return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y); } double mutil(node c0,node c1,node c2) { return (c1.x-c0.x)*(c2.y-c0.y)-(c2.x-c0.x)*(c1.y-c0.y); } int cmp(node c1,node c2) { int x=mutil(c1,c2,a[0]); if(x>0||(x==0&&dis(c1,a[0])<dis(c2,a[0]))) return 1; else return 0; } int cmp1(node a,node b) { if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } void Graham() { tot=2; p[0]=a[0],p[1]=a[1]; for(int i=2; i<n; i++) { while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0) tot--; p[tot++]=a[i]; } sort(p,p+tot,cmp1); for(int i=0;i<tot;i++) printf("%d %d\n",p[i].x,p[i].y); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d",&a[i].x,&a[i].y); } int k=0; for(int i=0; i<n; i++) { if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x)) k=i; } swap(a[0],a[k]); sort(a+1,a+n,cmp); // for(int i=0; i<n; i++) // { // printf("******%d %d\n",a[i].x,a[i].y); // } Graham(); } }
POJ-3348 Cows 入门求面积
void Graham() { tot=2; p[0]=a[0],p[1]=a[1]; for(int i=2; i<n; i++) { while(tot>1&&mutil(p[tot-1],p[tot-2],a[i])>=0) tot--; p[tot++]=a[i]; } int sum=0; for(int i=2; i<tot; i++) { int l=(int)mutil(p[0],p[i-1],p[i]); //在求面积的时候就可以直接用向量来求。即平行四边的面积 就等于两条边的乘积除以2； sum+=abs(l)/2; } printf("%d",sum/50); }
