【模板】二维凸包

link

奈何本人太弱，到现在才开始学习计算几何，连个凸包都写了半天……

本来用的第一篇题解里的啥啥方法没写出来，后来采用了另一种似乎更好理解的方法，算法名称鬼知道是什么也并不重要，于是就水过了。

思想很简单，一个凸包一定是由上下两部分组成的，从左往右来看，上半部分各边斜率单调递减，下半部分则单调递增，可以开个栈来维护这个过程，毕竟斜率优化那边就用的这个，然后求完两个凸壳拼起来就是一个完整的凸包了。写起来异常简单。

#include
#include
#include
#define zczc
using namespace std;
const int N=100010;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}

struct node{double x,y;}a[N],st[N];
inline bool cmp(node s1,node s2){return s1.x==s2.x?s1.y1&&!ck(st[top-1],st[top],st[top],a[i]))top--;
		st[++top]=a[i];
	}
	double ans=0;
	for(int i=1;i1&&!ck(st[top],a[i],st[top-1],st[top]))top--;
		st[++top]=a[i];
	}
	for(int i=1;i