Andrew 算法求凸包

参考资料：

右手定则(baidu.com)

内积和外积 - OI Wiki (oi-wiki.org)

• \(a\) 与 \(b\) 相对位置
  • \(b\) 在 \(a\) 的逆时针方向: \(a \times b>0\)
  • 顺负逆正（其实就是高中数学对于正负角的定义）

凸包 - OI Wiki (oi-wiki.org)

• 排序后最小和最大的元素为什么一定在凸包上？
• 单调栈维护上下凸壳
• 伪代码

while(右旋){
标记原来的栈顶为不在凸包上
}
标记新点在栈顶上
加入栈中

• 一般是叉积小于0则不合法（=0是平的，但合法）

二维凸包模板：Luogu P2742 Fencing the Cows

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
#define double long double 
using namespace std;
using ll = long long;
const int N=1e5+105;
struct node{
	double x,y;
	node operator - (const node &o)const{
		node z=(node){x-o.x,y-o.y};
		return z;
	}
	double operator * (const node &o)const{
		return x*o.y-y*o.x;
	}
	bool operator < (const node &o)const{
		return x==o.x ? y<o.y : x<o.x;
	}
}w[N];
double dis(node a){
	return __builtin_sqrt(a.x*a.x+a.y*a.y);
}
int tp=0,n;
int stk[N<<1];
bool used[N];
double ans=0;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n; F(i,1,n) cin>>w[i].x>>w[i].y;
	sort(w+1,w+n+1);
	stk[++tp]=1;//used不打标记方便最后封闭 
	F(i,2,n){
		while(tp>=2 && (w[stk[tp]]-w[stk[tp-1]])*(w[i]-w[stk[tp]])<0) used[stk[tp--]]=0;
		//注意叉积小于0,一定不能写成小于等于！ 
		used[i]=1;
		stk[++tp]=i;
	}
	G(i,n,1){
		if(used[i]) continue;
		while(tp>=2 && (w[stk[tp]]-w[stk[tp-1]])*(w[i]-w[stk[tp]])<0) used[stk[tp--]]=0;
		used[i]=1;
		stk[++tp]=i;
	}
	F(i,1,tp-1) ans+=dis(w[stk[i+1]]-w[stk[i]]);	
	ans+=dis(w[stk[1]]-w[stk[tp]]);
	cout<<fixed<<setprecision(2)<<ans<<"\n";
	return 0;
}