凸包簡介：

在二維平面上(二維凸包)給出若干個點，能夠包含這若干個點的面積最小的凸多邊形稱為凸包（可以想像有很多個釘子釘在墻上，然后用一個橡皮圈套在所有的釘子上，最后橡皮圈形成的就是一個凸包）。

 

Graham掃描法：

Graham掃描法是一種基于極角排序的進行求解的算法，其大致流程如下：

①找一個一定在凸包上的點P0（一般找縱坐標最小的點）；

②將其余所有的點以P0為基準進行極角排序；

③從P0出發掃描所有的點，不斷地更新最外圍的點，是否在最外圍可由叉乘判斷。這里用個圖說明一下：

當前對點P進行判斷，P1,P2為前面加入的兩個點：

Ⅰ）若點P在內部（圖一），則有向量b叉乘向量a小于零，此時點P是凸包的頂點，應將P點加入凸包。

Ⅱ）若在點P在外部，則有向量b叉乘向量a大于零，此時應該將點P1舍棄，繼續對前兩個點進行判斷，直到P、P1、P2三個點滿足向量b叉乘向量a小于零，再將P點加入凸包。

當然網上面還有更詳細的例子，不懂得話可以再看看其余的資料(￣▽￣)。

具體代碼如下：

//Graham掃描法-hdu1392
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
const double esp=1e-10;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;y=_y;
    }
}P[maxn],Convexhull[maxn];
typedef Point Vector;
Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double d){
    return Vector(A.x*d,A.y*d);
}
Vector operator / (Vector A,double d){
    return Vector(A.x/d,A.y/d);
}
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A){
    return sqrt(Dot(A,A));
}
int dcmp(double x){
    return fabs(x)<esp?0:x<0?-1:1;
}
bool Angle_Cmp(Point p1,Point p2){
    double res=Cross(p1-P[0],p2-P[0]);
    return dcmp(res)>0||(dcmp(res)==0&&dcmp(Length(p1-P[0])-Length(p2-P[0]))<0);
}
int Graham(int n){
    int k=0;
    Point p0=P[0];
    for(int i=1;i<n;i++){
        if(p0.y>P[i].y||(p0.y==P[i].y&&p0.x>P[i].x)){
            k=i;p0=P[i];
        }
    }
    swap(P[0],P[k]);
    sort(P+1,P+n,Angle_Cmp);
    Convexhull[0]=P[0];                 //Assume n>2
    Convexhull[1]=P[1];
    int top=2;
    for(int i=2;i<n;i++){
        while(top>1&&Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2])>=0)top--;
        Convexhull[top++]=P[i];
    }
    return top;
}
int main(){
    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
        int cnt=Graham(n);
        double ans=0;
        if(cnt!=2)ans+=Length(Convexhull[0]-Convexhull[cnt-1]);
        for(int i=0;i<cnt-1;i++)ans+=Length(Convexhull[i]-Convexhull[i+1]);
        printf("%.2lf\n",ans);
    }
    return 0;
}

 

Andrew算法：

Andrew算法是一種基于水平序的算法，在許多的資料上都會發現說該算法可以看作Graham掃描法的一種變體，為什么這么說呢？我的理解就是二者都是對所有的點進行掃描得到凸包，不過掃描之前做的處理不同，Andrew算法的大致流程如下：

①將所有的點按照橫坐標從小到大進行排序，橫坐標相同則按縱坐標從小到大排；

②將P[0]和P[1]加入凸包，然后從P[2]開始判斷，判斷方式同Graham算法中的判斷一致；

③將所有的點掃描一遍以后，我們便可以得到一個“下凸包”（為什么？畫個圖就懂了--橫坐標不會減小）；

④同理，我們從P[n-2]開始(P[n-1]已經判過了)，反著掃描一遍，便可以得到一個“上凸包”；

⑤將兩個“半凸包”合在一起就是一個完整的凸包，注意的是由于起點P[0]在正著掃描和反著掃描時都會將其加入凸包，故需要將最后一個點(P[0])去掉才為最終結果。

具體代碼如下：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
const double esp=1e-10;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;y=_y;
    }
}P[maxn],Convexhull[maxn];
typedef Point Vector;
Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double d){
    return Vector(A.x*d,A.y*d);
}
Vector operator / (Vector A,double d){
    return Vector(A.x/d,A.y/d);
}
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A){
    return sqrt(Dot(A,A));
}
int dcmp(double x){
    return fabs(x)<esp?0:x<0?-1:1;
}
bool operator <(Point p1,Point p2){
    return dcmp(p1.x-p2.x)<0||(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)<0);
}
int Andrew(int n){      //Assume n>2
    sort(P,P+n);
    int top=0;
    for(int i=0;i<n;i++){
        while(top>1&&dcmp(Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2]))>=0)top--;
        Convexhull[top++]=P[i];
    }
    int k=top;
    for(int i=n-2;i>=0;i--){
        while(top>k&&dcmp(Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2]))>=0)top--;
        Convexhull[top++]=P[i];
    }
    return top-1;
}
int main(){
    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
        int cnt=Andrew(n);
        double ans=0;
        if(cnt!=2)ans+=Length(Convexhull[0]-Convexhull[cnt-1]);
        for(int i=0;i<cnt-1;i++)ans+=Length(Convexhull[i]-Convexhull[i+1]);
        printf("%.2lf\n",ans);
    }
    return 0;
}

 

小結：

顯然兩種算法的復雜度均為O(nlogn)，若輸入有序的話時間復雜度就均為O(n)，但是紫薯上說“和原始的Graham算法相比，Andrew算法更快，且數值穩定性更好”，或許是因為排序二者排序過程中的差異--Graham算法中的極角排序需要進行大量的叉乘計算。