【凸包】

例题：cogs圈奶牛

叶子最可爱了

算法流程：

找左下点，以其为原点极角排序，队列维护凸包点。

算法实现：

一、左下点扫一遍

二、极角排序重载运算符，通过向量叉积判断极角大小，若极角相同则与参照点距离小者优先。

三、维护队列，加入点便在队列末端进行叉积判断极角。极角只能越来越大。

叉积

对于两个向量A,B，AxB=Xa*Yb-Xb*Ya;计算结果绝对值为两向量构成的平行四边形面积，不加绝对值称为有向面积。

如果结果大于0，则说明A的极角比B小，反之比B大。我称为“正下负上”。

明显对于一个三角形面积，任取两条边叉积除以2取绝对值即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
struct node{
	double x,y;
	node friend operator -(node a,node b){
		return {a.x-b.x,a.y-b.y};
	}
}a[10003],p[10003];
int n,tail;
double operator ^(node a,node b){
	return a.x*b.y-a.y*b.x;
}
double dis(node a,node b){
	node c=a-b;
	return sqrt(c.x*c.x+c.y*c.y);
}
double get(node a){
	return atan2(a.y,a.x);
}
bool cmpp(node A,node B){
	double c=get(A-a[1]),d=get(B-a[1]);
	if(c==d)return dis(a[1],A)<dis(a[1],B);
	return c<d;
}
int main(){
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	n=in;
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&a[i].x,&a[i].y);
	}
	if(n==1){
		printf("0.00");return 0;
	}
	if(n==2){
		printf("%.2lf",dis(a[1],a[2]));return 0;
	}
	int k=1;
	for(int i=2;i<=n;i++){
		if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))k=i;
	}
	swap(a[1],a[k]);
	sort(a+2,a+n+1,cmpp);
	p[++tail]=a[1],p[++tail]=a[2];
	for(int i=3;i<=n;i++){
		while(tail>=2&&((p[tail]-p[tail-1])^(a[i]-p[tail-1]))<=0)tail--;
		p[++tail]=a[i];
	}
	double sum=0;
	for(int i=1;i<tail;i++)sum+=dis(p[i],p[i+1]);
	printf("%.2lf",sum+dis(p[1],p[tail]));
	return 0;
}