凸包
关于凸包
概念：在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为 X的凸包。X的凸包可以用X内所有点(X1，...Xn)的凸组合来构造；
简单来说：给你一个点集Q,你可以把Q中的每个点想象成一块木板上的铁钉，而点集Q的凸包就是包围了所有铁钉的一条拉紧了橡皮绳所构成的形状；
在构造凸包时，有两种情况，一种是上凸包，一种是下凸包；
在构造之前，我们需要先对这些点进行排序，按照x轴从小到大排，x相等时按照y轴从小到大排；
例子
练习
原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=1392
题目要求： 求凸包的周长
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 using namespace std; struct node { double j,k; }; node a[105],res[105]; ///数组a用来记录所有的点，数组res用来记录凸包的点 bool cmp(node x,node y) { if (x.j!=y.j) return x.j<y.j; return x.k<y.k; } double cross(node a, node b, node c) /// × 乘 { return (a.j-c.j)*(b.k-c.k)-(a.k-c.k)*(b.j-c.j); } double dis(node a,node b) ///计算两点距离 { return sqrt((a.j-b.j)*(a.j-b.j)+(a.k-b.k)*(a.k-b.k)); } int main () { int n,m,i,t; while(scanf("%d",&n) ) { if (n==0) break; for(i=0;i<n;++i){ scanf("%lf %lf",&a[i].j,&a[i].k); } if (n==1) ///n为1，2时要特判一下 { printf("0.00 "); continue; } if (n==2) { printf("%.2f ",dis(a[0],a[1])); continue; } sort(a,a+n,cmp); res[0]=a[0]; res[1]=a[1]; t=2; for(i=2;i<n;++i) ///下凸包 { while(t>=2 && cross(a[i],res[t-1],res[t-2])>0 ) t--; res[t]=a[i]; t++; } int p=t; for (i=n-2;i>=0;--i) ///上凸包 { while(t>=p && cross(res[t-1],a[i],res[t-2])<0 ) t--; res[t]=a[i]; t++; } double sum=0; t--; for(i=0;i<t;++i) sum+=dis(res[i],res[i+1]); printf("%.2f ",sum); } return 0; }