神奇地，在这份题单中，计算几何甚至没划在“数学”里面，于是我也借鉴了才不是为了水篇数呢。

凸包

以P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包为例。

Garham算法

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;using ll = long long; 
namespace ugi{
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using ugi::in;
const int maxn=100012;double eps=1e-10;
int n;
struct pt
{
    double x,y,avg;
    double operator*(const pt b)const
    {
        return x*b.y-y*b.x;
    }
    pt operator-(pt b)
    {
        return (pt){x-b.x,y-b.y,0};
    }
}nl[maxn],st;
int sta[maxn],tot;
double dis(const pt a,const pt b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(const pt a,const pt b)
{
    return fabs(a.avg-b.avg)>eps?a.avg<b.avg:dis(a,st)<dis(b,st);//同线更远
}
int main()
{
    scanf("%d",&n);
    st.y=1000012;
    fru(i,1,n)
    {
        scanf("%lf%lf",&nl[i].x,&nl[i].y);
        if(nl[i].y<st.y)st=nl[i];
    }
    double t;
    fru(i,1,n)
    {
        t=dis(nl[i],st);
        if(fabs(t)>eps)//防止重合
        {
            nl[i].avg=acos((nl[i].x-st.x)/t);
        }
    }
    sort(nl+1,nl+n+1,cmp);
    sta[++tot]=1;
    fru(i,2,n)
    {
        while(tot>=2&&(nl[sta[tot]]-nl[sta[tot-1]])*(nl[i]-nl[sta[tot]])<0)tot--;//Garham算法的共线一定不能在这处理，不像Andrew，它会折返！
        sta[++tot]=i;
    }
    double ans=dis(nl[1],nl[sta[tot]]);
    fru(i,1,tot-1)ans+=dis(nl[sta[i]],nl[sta[i+1]]);
    printf("%.2lf",ans);
    return 0;
}