入门二维凸包

算法概述

考虑平面上的若干个无序分布的点，要用一根橡皮筋框柱所有点（橡皮筋绷在点上），橡皮筋所受弹力方向只能向外。这跟橡皮筋及橡皮筋所框柱的区域就叫做一个凸包；橡皮筋叫做凸壳。

书面地，对于平面内的点集 \(X\)，所有完全包含它的凸多边形的交集叫做 \(X\) 的凸包（Convex Heap）。
其中，凸多边形为所有内角 \(\in[0,\pi]\) 的多边形。

求凸包的算法有 Graham 和 Andrew 两种，Andrew 是前者的变种，且更快更稳定，因此一般只需学习 Andrew。
Andrew 算法时间复杂度 \(O(n\log n)\)，瓶颈在排序。下面介绍该算法。

将所有点以 \(x\) 为第一关键字、\(y\) 为第二关键字从小到大排序。容易发现，第一个点和最后一个点一定为凸壳上的点。

首先找到下凸壳，此时已经遍历完了一次；仿照以上找到上凸壳（倒序遍历），此时又回到第一个点。因此只需想好怎么找下凸壳。

算法的思想为，顺序枚举每一个点，即时找到这条能“兜住”已经遍历过的所有点的下凸壳（按序塞到一个栈中）。那么局部类似整体，当前点一定是这条凸壳的末端点。

考虑上图。一个向量和下一个向量时刻满足下一个向量在这个向量的逆时针方向。那么一旦向量 \(\bm{P_{i-2}P_{i-1},P_{i-1}P_i}\) 不满足后者在前者的逆时针方向，则说明 \(P_{i-1}\) 一定是找错了，应该退出凸壳。利用 while 循环对栈顶元素重复判断并弹出，则可以维护一个类似单调栈的节点序列，末了栈中元素自底而上便是凸壳点序列。
顺逆时针的判断利用向量叉积。
最开始栈中只有第一个点，从二号点开始遍历。

一些细节：特殊情况凸包为一直线，凸壳点可能会重复（一来一回），因此往往存整个凸包点序列的数组需要开到二倍点数的大小。

//https://www.luogu.com.cn/problem/P2742
#include 
#define sq(a) (a)*(a)
using namespace std;
const int N=1e5+5;
int n,tp,stk[N],h[N<<1];
struct P{double x,y;}a[N];
bool operator<(P a,P b){
	if(a.x==b.x)return a.y>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;
	stk[++tp]=1;
	for(int i=2;i<=n;i++){
		while(tp>1&&(a[stk[tp]]-a[stk[tp-1]])*(a[i]-a[stk[tp]])<0)tp--;
		stk[++tp]=i;
	}
	for(int i=1;i<=tp;i++)h[i]=stk[i];
	int tmp=tp;
	stk[tp=1]=n;
	for(int i=n-1;i;i--){
		while(tp>1&&(a[stk[tp]]-a[stk[tp-1]])*(a[i]-a[stk[tp]])<0)tp--;
		stk[++tp]=i;
	}
	for(int i=1;i<=tp;i++)h[i-1+tmp]=stk[i];
	int m=tp-2+tmp; double ans=0;
	for(int i=1;i<=m;i++)ans+=sqrt(sq(a[h[i]].x-a[h[i+1]].x)+sq(a[h[i]].y-a[h[i+1]].y));
	printf("%.2f",ans);
}

事实上，弹栈部分还有另一种写法，将 -a[stk[tp]] 改成 -a[stk[tp-1]]，效果是一样的，请读者自己思考。

练习

• [SHOI2012]信用卡凸包