凸包 首先 极角排序, 选一个初始的点。然后，自己去看吧，说不清楚。

 

洛谷上过了两个模板题，看题解 和OI wiki 

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

　　

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4+10;
int n,cnt;
struct Point{
    double x,y;
}p[N],s[N];

double dist(Point a,Point b)
{
    return sqrt( (a.x -b.x)*(a.x - b.x) + (a.y -b.y) * (a.y -b.y));
}
double cross(double x1, double y1, double x2, double y2)
{
    return (x1 * y2 - x2 * y1);    
}
double check(Point a,Point b,Point c,Point d)
{
    return cross(b.x - a.x, b.y - a.y, d.x - c.x ,d.y - c.y);
}

bool cmp(Point p1,Point p2)
{
     double tmp=check(p[1],p1,p[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dist(p[0],p1)<dist(p[0],p2)) 
		return 1;
    return 0;
}
int main()
{
    cin>>n;
 
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lf%lf",&p[i].x, &p[i].y);
        if(i!=1&&(p[i].x <p[1].x ||p[i].x == p[1].x && p[i].y <p[1].y))//这是是去重 
        {
            swap(p[i],p[1]);
        }
    }
    sort(p + 2,p + n + 1,cmp);
    // for(int i = 1;i <= n ;i ++) cout<<p[i].x<<","<<p[i].y<<endl;
    s[1] = p[1];
    cnt = 1;
    for(int i = 2; i <= n; i ++)
    {
        while(cnt > 1 && check(s[cnt - 1], s[cnt], s[cnt], p[i]) <= 0)
            cnt --;
        cnt ++;
        s[cnt] = p[i];
    }
    s[cnt + 1] = p[1];
    double ans = 0;
    //cout<<p[1].x<<" "<<p[1].y<<endl;
    for(int i = 1; i <= cnt; i ++)
    {
        // cout<<dist(s[i], s[i + 1])<<endl;
        ans += dist(s[i], s[i + 1]);
    }
    printf("%.2lf",ans);
    return(0);
}

　　

P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n,cnt;
struct Point{
    int x,y;
}p[N],s[N];

LL dist(Point a,Point b){
    return (a.x -b.x)*(a.x - b.x) + (a.y -b.y) * (a.y -b.y);
}
LL cross(int x1, int y1, int x2, int y2){
    return (x1 * y2 - x2 * y1);    
}
LL check(Point a,Point b,Point c,Point d){   //可以算用来复用算面积
    return cross(b.x - a.x, b.y - a.y, d.x - c.x ,d.y - c.y);
}
bool cmp(Point p1,Point p2){
    LL tmp=check(p[1],p1,p[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dist(p[0],p1)<dist(p[0],p2)) 
		return 1;
    return 0;
}
LL getMax() //求凸包的直径
{
    if(cnt == 2) return dist(s[1],s[2]);
    else
    {
        int j = 3;
        LL ans = 0;
        for(int i = 1;i <= cnt; i ++)
        {
            while(check(s[i],s[i+1],s[i],s[j]) < check(s[i],s[i+1],s[i],s[j+1]))
                 j = j % cnt + 1; //这个地方注意了 之前写的虽然过了但是误打误撞出来的
            ans=max(ans,max ( dist(s[i],s[j]), dist(s[i+1],s[j])) );
        }
        return ans;
    }
}

int main()
{
    cin>>n;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d%d",&p[i].x, &p[i].y);
        if(i > 1 && (p[i].x < p[1].x || p[i].x == p[1].x && p[i].y < p[1].y)) //这里是为了三个点一条线时应选取最长的线段，故意造数据卡
            swap(p[1],p[i]);
    }
    sort(p + 2,p +  n + 1,cmp);
    cnt=1;
    s[1] = p[1];
   for(int i = 2; i <= n; i ++)
    {
        while(cnt > 1 && check(s[cnt - 1], s[cnt], s[cnt], p[i]) <= 0)
            cnt --;
        cnt ++;
        s[cnt] = p[i];
    }
    // cout<<cnt<<endl;
    // for(int i=1;i<=cnt;i++) cout<<s[i].x<<" "<<s[i].y<<endl;
    s[cnt + 1] = p[1];
   
    //凸包部分完成
    LL ans = getMax();
    printf("%lld",ans);
    return(0);
}