所謂凸包，就是一個凸出來的包

（逃）

前言

解析集合的第一課。
關鍵特征：周長最小。此時一定是凸包。

解析

定義

凸包：在平面上能包含所有給定點的最小凸多邊形叫做凸包。

性質：凸包的周長是所有能包含給定點的多邊形中最小的。

維護

凸包的主流求法有 Andrew 和 Graham，兩者的復雜度瓶頸都在于排序，為 $O(n\log n)$。
這里介紹較為簡單的 Graham 掃描法。

首先，找出所有點中按照 $X?Y$ 排序最小的點 $O$。
然后以 $O$ 作為原點，把所有其它點按照極角排序，極角相同時按距離升序排序（實測這里也可以降序，但是絕對不能無序）。
可以用快排重載 cmp 函數的方法實現，利用叉積判斷。

bool cmp(V a,V b){double d=(a-p[1])^(b-p[1]);if(abs(d)>eps) return d>0;else return len(a-p[1])<len(b-p[1]); }

排好序后，開一個棧維護當前凸包中的點。
如果新點破壞了凸性，則不斷退棧。
最終棧內的元素就是凸包中的點。

是否破壞凸性可以用叉積判斷，如果新點和棧頂形成的向量向右拐了（叉積小于0），則說明破壞了凸性。

注意：這里判斷退棧的條件最好帶等！，一方面，共線時在邊上的頂點沒有什么意義，另一方面，當有重合點時，不帶等會導致程序錯誤。

void ConvexHull(V *p,int &n){int top=0;sort(p+1,p+1+n);sort(p+2,p+1+n,cmp);top=0;for(int i=1;i<=n;i++){while((top>1&&((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))<=0)) --top;zhan[++top]=p[i];}memcpy(p,zhan,sizeof(zhan));n=top;return; }

完整代碼

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二維凸包

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }//basic declare //#define double long double const double eps=1e-10; const double pi=acos(-1.0);//---about vectors (or points)//definition struct V{double x,y;V():x(0),y(0){}V(double a,double b):x(a),y(b){} }; V ans[10];//declared for other functions int tot; inline void input(V &a){scanf("%lf%lf",&a.x,&a.y);} void print(const V &a,int op=1){printf("%.10lf %.10lf",a.x,a.y);putchar(op?10:32);} //op:endl or space//basic operation inline V operator + (const V &a,const V &b){return (V){a.x+b.x,a.y+b.y};} inline V operator - (const V &a,const V &b){return (V){a.x-b.x,a.y-b.y};} inline V operator * (const double &x,const V &a){return (V){a.x*x,a.y*x};} inline V operator * (const V &a,const double &x){return (V){a.x*x,a.y*x};} inline V operator / (const V &a,const double x){return (V){a.x/x,a.y/x};} inline bool operator == (const V &a,const V &b){return abs(a.x-b.x)<eps&&abs(a.y-b.y)<eps;} inline bool operator != (const V &a,const V &b){return !(a==b);} inline double operator * (const V &a,const V &b){return a.x*b.x+a.y*b.y;} inline double operator ^ (const V &a,const V &b){return a.x*b.y-a.y*b.x;} inline double len(const V &a){return sqrt(a.x*a.x+a.y*a.y);} inline V mid(const V &a,const V &b){return (V){(a.x+b.x)/2,(a.y+b.y)/2};} inline V chui(const V &a){return (V){a.y,-a.x};}//not take direction into account inline V danwei(const V &a){return a/len(a);} inline double tri_S(const V &a,const V &b,const V &c){return abs((b-a)^(c-a))/2;}//always be non-negative inline bool operator < (const V &a,const V &b){return a.x<b.x-eps||(abs(a.x-b.x)<eps&&a.y<b.y-eps); } inline double ang(const V &a,const V &b){return acos((a*b)/len(a)/len(b));} inline V rotate(const V &o,double t){//COUNTER_CLOCKWISEdouble s=sin(t),c=cos(t);return (V){o.x*c-o.y*s,o.x*s+o.y*c}; }const int N=1e5+100; const int M=505; int n,m; V p[N],zhan[N]; bool cmp(V a,V b){double d=(a-p[1])^(b-p[1]);if(abs(d)>eps) return d>0;else return len(a-p[1])<len(b-p[1]); } void ConvexHull(V *p,int &n){int top=0;sort(p+1,p+1+n);sort(p+2,p+1+n,cmp);top=0;for(int i=1;i<=n;i++){while((top>1&&((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))<eps)) --top;zhan[++top]=p[i];}memcpy(p,zhan,sizeof(zhan));n=top;return; } signed main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifn=read();for(int i=1;i<=n;i++) input(p[i]);ConvexHull(p,n);zhan[n+1]=p[1];double res(0);for(int i=1;i<=n;i++) res+=len(zhan[i+1]-zhan[i]);//print(zhan[i]);printf("%.2lf\n",res);return 0; } /* 3 5 0 -2 -5 3 0 -7 */

總結

以上是生活随笔為你收集整理的模板：二维凸包（计算几何）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。