还是写了一个好懂点的凸包模板
#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);
}
}
