凸包学习小记

向量（矢量）

既有大小，又有方向的量，如速度
表示方法：字母上加箭头 \(\overrightarrow{a}\)
若向量起点为 \(A\) 终点为 \(B\) 向量可表示为 \(\overrightarrow{AB}\)
向量的大小：表示为 \(|\overrightarrow{a}|\) 或 \(|\overrightarrow{AB}|\)
零向量：\(\overrightarrow{O},|\overrightarrow{O}|=O\)，起点和终点重合，方向任意
单位向量：长度为一个单位的向量
在平面直角坐标系中，将向量 \(\overrightarrow{a}\) 平移，使起点和原点重合，终点位于点 \((x,y)\) ，

则实数对 \((x,y)\) 为向量 \(\overrightarrow{a}\) 的坐标，记为 \(\overrightarrow{a}=(x,y)\) 。
加法：\(\overrightarrow{A}+\overrightarrow{B}=(x_1+x_2,y_1+y_2)\)
向量加法满足交换律和结合律
减法 \(\overrightarrow{A}-\overrightarrow{B}=(x_1-x_2,y_1-y_2)\)
已知 \(A(x_1,y_1),B(x_2,y_2)\)，则\(\overrightarrow{AB}=B-A\)

点积

点积就是 \(a\cdot b=x_1x_2+y_1y_2\)
几何意义：两个向量的夹角。
点积有以下性质

\(a\cdot b=0\)，则 \(a\perp b\)
\(a\cdot b<0\)，则夹角 \(>90^\circ\)
\(a\cdot b>0\)，则夹角 \(<90^\circ\)

叉积

叉积就是 \(a\times b=x_1y_2-x_2y_1\)
几何意义：两个向量的起点共点时，所形成的平行四边形面积
性质

\(a\times b=0\)，a 和 b 平行
\(a\times b>0\)，a 在 b 顺时针方向
\(a\times b<0\)，a 在 b 逆时针方向

凸包

平面凸包是指覆盖平面上n个点的最小的凸多边形，一般题目都会要求求周长

Graham 扫描法

找到最左下的点作为原点
将其他点与远点连一条线段，计算出线段与水平线的夹角，按这些夹角排序。

若存在夹角相同，优先选择 x 坐标小的点
维护一个栈，将前两个点放进栈中，遍历 3~n。
- 若栈顶的两个点和当前的点这三点连线的方向向顺时针方向偏转
  
  表明栈顶的点是一个凹陷处，应删除，栈顶元素出栈，并将当前点压入栈中。
- 如果向逆时针方向偏转，则直接压入栈中
遍历完后，栈中的点就是凸包上的点，周长为 \(\sum_{i=1}^{top}|\overrightarrow{s_is_{i+1}}|\)
atan2 函数，atan2(double x,double y) 返回 \(\overrightarrow{A}=(x,y)\) 与 x 轴的夹角，用于排序

Code

例： [USACO5.1] Fencing the Cows

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct vec { double x,y; }p[N],st[N];
inline double Times(vec A,vec B,vec C) {
	// (B-A) * (C-A)
	return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline double Dis(vec A,vec B) {
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
inline bool Cmp(vec u,vec v) {
	register double A=atan2(u.y-p[1].y,u.x-p[1].x),
		B=atan2(v.y-p[1].y,v.x-p[1].x);
	return A==B?u.x<v.x:A<B;
}
int n,top;
double ans;
inline void Graham() {
	register int k=0;
	p[0].x=p[0].y=2100000000;
	for(int i=1;i<=n;i++)
		if(p[0].y>p[i].y || (p[0].y==p[i].y && p[0].x>p[i].x))
			p[0]=p[i],k=i;
	swap(p[1],p[k]);
	sort(p+2,p+n+1,Cmp);
	st[0]=p[1],st[1]=p[2],top=1;
	for(int i=2;i<=n;i++) {
		while(top && Times(st[top-1],p[i],st[top])>=0)--top;
		st[++top]=p[i];
	}
	// Compute
	st[top+1]=p[1];
	for(int i=0;i<=top;i++)
	ans+=Dis(st[i],st[i+1]);
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	Graham();
	printf("%.2lf",ans);
}

信用卡凸包

SHOI 2012

题目大意

求圆弧卡片包含圆弧的凸包周长

转换

结论：最终凸包的圆弧总长恰好等于一个给定半径为 r 的圆的周长。

于是问题转化为求圆的周长+圆心构成的凸包的周长

关于旋转

设当前点为 \(A(x,y)\) ，将 \(A\) 绕原点 O 旋转 \(\theta^\circ\) 后得到 \(A^\text{'}\) ，则 \(A^\text{'}(x\cdot\cos\theta^\circ-y\cdot\sin\theta^\circ,y\cdot\cos\theta^\circ+x\cdot\sin\theta^\circ)\)

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct vec {
	double x,y;
	vec(double p=0,double q=0): x(p),y(q) { }
	vec operator +(vec o) { return vec(x+o.x,y+o.y); }
	vec operator -(vec o) { return vec(x-o.x,y-o.y); }
}p[N],st[N];
int n,cnt,top;
double a,b,r,x,y,theta,ans;
vec Rotate(vec x,vec o,double rot) {
	register double cs=cos(rot),si=sin(rot);
	return x=x-o,vec(x.x*cs-x.y*si,x.y*cs+x.x*si)+o;
}
inline double Times(vec A,vec B,vec C) {
	// (B-A) * (C-A)
	return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline double Dis(vec A,vec B) {
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
inline bool Cmp(vec u,vec v) {
	register double A=atan2(u.y-p[1].y,u.x-p[1].x),
		B=atan2(v.y-p[1].y,v.x-p[1].x);
	return A==B?u.x<v.x:A<B;
}
inline void Graham() {
	register int k=0;
	p[0].x=p[0].y=2100000000;
	for(int i=1;i<=cnt;i++)
		if(p[0].y>p[i].y || (p[0].y==p[i].y && p[0].x>p[i].x))
			p[0]=p[i],k=i;
	swap(p[1],p[k]);
	sort(p+2,p+cnt+1,Cmp);
	st[0]=p[1],st[1]=p[2],top=1;
	for(int i=2;i<=cnt;i++) {
		while(top && Times(st[top-1],p[i],st[top])>=0)--top;
		st[++top]=p[i];
	}
	// Compute
	st[top+1]=p[1];
	for(int i=0;i<=top;i++)
		ans+=Dis(st[i],st[i+1]);
	ans+=2*r*acos(-1.0);
}
int main() {
	scanf("%d%lf%lf%lf",&n,&a,&b,&r);
	a/=2.0,b/=2.0;
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf%lf",&x,&y,&theta);
		p[++cnt]=Rotate(vec(x+(b-r),y+(a-r)),vec(x,y),theta);
		p[++cnt]=Rotate(vec(x+(b-r),y-(a-r)),vec(x,y),theta);
		p[++cnt]=Rotate(vec(x-(b-r),y+(a-r)),vec(x,y),theta);
		p[++cnt]=Rotate(vec(x-(b-r),y-(a-r)),vec(x,y),theta); 
	} 
	Graham();
	printf("%.2lf",ans);
}