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

预告

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