HAO的Graham学习笔记

前置知识：凸包

摘录oiwiki

在平面上能包含所有给定点的最小凸多边形叫做凸包。
其定义为：对于给定集合 X，所有包含 X 的凸集的交集 S 被称为 X 的 凸包。

说人话就是用一个橡皮筋包含住所有给定点的形态

如图：

正题：Graham求凸包

过程

Graham求凸包的过程是：
1，选一个点，其它点以它作为标准将其他点进行极角排序
两种方法，建议使用atan2(懒)
atan2用法：atan2(横坐标，纵坐标）（注：以选择的点为原点的坐标）

2，从最低的点开始（这能保证第一个点一定在凸包内）枚举
分成两种情况：

if 上一个点在这个点的左边{将这个点加入答案
}
else{将这个点pop
}

此处可用叉积判断左右，叉积学习
3，连接第一个点与最后一个点
分析时间复杂度
处理时每个点只会一次，即为O(n),n为点数，还有角排序的O(nlog(n)),总体为O(n+nlog(n))

实例

如果下一个点在右边像这样
(原应从第一个点连了第二点后直接连最右下的点，但我这画错了，致歉）
很明显，将上一个点排出，因为当前的点劣于当前点（当前点在上个点右边）

变成了这样

发现当前的点还是优于最后一个点（在其右），排出
在上一点的左边，加入
其它的都在左边不在赘述
结果就是：

有一个很好的演示视频，放在这（看了就去支持那个up吧，sto颓废orz）
演示视频

代码实现

模版

First,初始化每个点的极角度数（此处为atan2实现）

	//p是存点的，x是行，y是列，与平面直角坐标系完全相反//p[1]是最低的点，以p[1]为原点for(int i=1;i<=n;i++){p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y);}

Second,排序（以极角排(大的先)，相同就以在p[1]右来排序）

bool cmp(node x,node y){if(x.angle==y.angle){return ju(x,p[1])>ju(y,p[1]);}return x.angle>y.angle;
}

Third 开始处理（以单调栈维护答案）

	st[++top]=p[1];for(int i=2;i<=n;i++){while(top>=2&&jiao(st[top]-st[top-1],p[i]-st[top])<0){top--;}st[++top]=p[i];}st[top+1]=p[1];

完整代码
这个代码是P2742的，凸包模版题
请勿 Ctrl-A+Ctrl-C+Ctrl-V 丝滑小连招，请自己了解后手打一遍

#include<bits/stdc++.h>
using namespace std;
struct node{double x,y;double angle;node operator-(const node p)const{return{x-p.x,y-p.y,0};}
}p[100001];
int n;
int s1[10001];
double ju(node x,node y){//求距离 return sqrt((x.y-y.y)*(x.y-y.y)+(y.x-x.x)*(y.x-x.x));
}
bool cmp(node x,node y){//角排序 if(x.angle==y.angle){return ju(x,p[1])>ju(y,p[1]);}return x.angle>y.angle;
}
double jiao(node x,node y){//叉积 return x.x*y.y-x.y*y.x;
}
node st[100001];
int top;
int main(){cin>>n;int k,xx,yy;for(int i=1;i<=n;i++){cin>>p[i].y>>p[i].x;if(i==1){k=i;xx=p[i].x;yy=p[i].y;}if(p[i].x<xx||(p[i].x==xx&&p[i].y<yy)){k=i;xx=p[i].x;yy=p[i].y;}}swap(p[k],p[1]);for(int i=1;i<=n;i++){p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y);}sort(p+2,p+n+1,cmp);st[++top]=p[1];for(int i=2;i<=n;i++){while(top>=2&&jiao(st[top]-st[top-1],p[i]-st[top])<0){top--;}st[++top]=p[i];}st[top+1]=p[1];double ans=0;for(int i=1;i<=top;i++){ans+=ju(st[i],st[i+1]);
//		cout<<st[i].x<<" "<<st[i].y<<endl;}printf("%.2lf",ans);
}

例题：P3829

题意：给你一堆给出的卡片，求其凸包周长（凸包长度包含圆弧长度）
分析第三个样例：

其中的黑色凸包与答案红色部分的长度完全相同，在根据我们小学8年级的知识：多变形的外角和为360度，所以外面的圆弧刚好就是一个圆，答案就等于凸包+一个圆的长度。
代码：我不贴了

预告

可能会出Andrew的笔记，那时会用Andrew写一遍P3829