自己看的懂的凸包模板

还是写了一个好懂点的凸包模板

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;

struct point
{
    int x,y;
}p[1005],s[1005];

/*叉积计算*/

int det(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;
}

/* 求倒数第二个点和倒数第一个点,与倒数第一个点与当前点的叉乘*/
int cross(point o,point a,point b)
{
    return det(a.x-o.x,a.y-o.y,b.x-o.x,b.y-o.y);
}

/*求平方*/

db f(int x)
{
    return x*x*1.0;
}

/*水平排序*/

bool cmp(point a,point b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

db dis(point a,point b)
{
    return sqrt(f(a.x-b.x)+f(a.y-b.y));
}

int n,l;

int main()
{
    while(scanf("%d %d ",&n,&l)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d %d",&p[i].x,&p[i].y);
        sort(p,p+n,cmp);
        int top=0;//正起扫一遍
        for(int i=0;i<n;i++)
        {
            while(top>=2 && cross(s[top-2],s[top-1],p[i])<0)//大于0,小于0完全看你向量的指向与谁相当于谁,
                                                             这个还是挺复杂的千万逻辑要清楚啊.
                top--;
            s[top++]=p[i];
        }
        int t=top+1;//反着再扫一遍
        for(int i=n-2;i>=0;i--)
        {
            while(top>=t && cross(s[top-2],s[top-1],p[i])<0)
                top--;
            s[top++]=p[i];
        }//凸包构建完成.
      int ans=0;
        for(int i=0;i<top-1;i++)
            ans+=dis(s[i],s[i+1]);//把凸包的所有边长求出来.
        printf("%d\n",ans);
    }
}