计算几何训练笔记

Luogu1452 旋转卡壳，注意判一下平行的情况，另外有个比较简介的求凸包方法，就不用分别求上凸壳和下凸壳再合起来了：

int is(point a,point b){return a.x==b.x?a.y<b.y:a.x<b.x;}
#define pd(A,B,C) (cross((C-B),(B-A))>0||(cross((C-B),(B-A))==0&&is(A,B)==is(B,C)))

sort(p+1,p+n+1,is);
int cnt=0,i;
for(i=1;i<=n;all[++cnt]=i++) while(cnt>1&&pd(p[all[cnt-1]],p[all[cnt]],p[i])) --cnt;
for(i=n-1;i;all[++cnt]=i--) while(cnt>1&&pd(p[all[cnt-1]],p[all[cnt]],p[i])) --cnt;--cnt;

all 存的就是凸包点的编号

然后旋转卡壳注意可以用面积判断点离线段距离的长短，然后每次统计答案需要 \(j\) 和 \(j+1\) 的两个点都需要更新答案。