向量有方向与长度
两个点可以得到一个向量,如果交换点对位置，向量的方向也会取反。
要注意的是，向量本身只有方向和长度。
方便起见，我们可以简单地用二元组\((x,y)\)表示一个向量，即默认起点为原点\((0,0)\)。
向量与一般数的运算，几何意义上，向量乘以某个数x等价于将向量放大\(x\)倍。
一般的，向量\((x,y)*k = (kx,ky)\)
向量与向量的运算。
加减就直接对应分量相加减就好了，几何意义如下图。
乘法,向量的乘法分为两种，点乘与叉乘。
也叫内积，数量积，几何意义由余弦定理得来，在上图的三角形ADB中，运用余弦定理就可以了
定义:\(a*b=|a||b|cos\theta\)
\(\theta\)为向量间的夹角，角度从A->B看，即b在a的顺时针方向多少度
当用二元组表示时,形式如下，
\((x_1,y_1)*(x_2,y_2) = (x_1y_1,x_2y_2)\)
点积的几何意义为\(a\)在\(b\)上的模长乘上\(b\)的长度，过\(a\)端点向\(b\)做垂线即可看出。
也叫外积，向量积
定义:\(a\times b=|a||b|sin{\theta}\)
当用二元组表示时，形式如下，
\((x_1,y_1)\times(x_2,y_2)=x_1y_2-x_2y_1\)
叉积的数量上的意义为对应平行四边形的面积，几何上好像对应一个更高维的向量，这个暂时用不到。
将向量\(\overrightarrow{a}=(x,y)\)旋转角度\(\theta\)的公式为
\((x_1,y_1) \rightarrow (x_1cos\theta+y_1sin\theta,x_1sin\theta+y_1cos\theta)\)
我们设\(\overrightarrow{a}\)的极角为\(\beta\)
向量\(\overrightarrow{a}=(|a|cos\beta,|a|sin\beta)\)
旋转后得到的新向量\(\overrightarrow{a'}=(|a|cos(\beta+\theta),|a|sin(\beta+\theta))\)
运用和角公式
\(sin(\alpha+\beta)=sin\alpha cos\beta+cos\alpha sin\beta\)
\(cos(\alpha+\beta)=cos^2\alpha+sin^2\beta\)
展开化简即得。
\(1.\)求夹角
\(\theta=cos^{-1}(\frac{a*b}{|a||b|})\)
\(2.\)判断两个向量的相对位置
判断\(a\times b\)的正负即可
\(3.\)求一个向量在另一个向量上的投影长度
\(Length=\large\frac{a*b}{|b|}\)
\(4.\)点到向量距离
\(a\)为向量，b为向量端点与点的向量
原理:\(h=\frac{S}{a}\)
\(Length=\large\frac{a\times b}{|a|}\)
给出平面上的n个点，凸包为最小的能将其全部包含在内的凸多边形。
显而易见，凸包的顶点一定在原点集中。
Graham 扫描法
先求上凸壳，将点按横坐标排序，依次加入一个斜率递减的单调栈中即可，
假设最后加入的点为A,B
如果当前加入的点C与A形成的向量在AB的左侧，ABC为凹的，B已经失去作用，可以从单调栈中弹出。
不断弹出直到满足凸多边形的性质即可。
具体判断斜率时，我们可以使用叉积的性质来判断，这样就可以有效的避免一些边界判断。
下凸壳同理。
执行部分\(O(n)\),排序\(O(nlog_2n)\)
总时间复杂度\(O(nlog_2n)\)
代码很短
洛谷凸包模板P2742的AC 代码\((C++11)\)
/*
@Date : 2019-07-12 18:11:10
@Author : Adscn (1349957827@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
const int N=1e4+10;
struct Vector{double x,y;};
struct Point{
double x,y;
explicit Point(double _x,double _y):x(_x),y(_y){}
Point(){}
}p[N];
istream& operator >> (istream &is,Point &x){
scanf("%lf%lf",&x.x,&x.y);
return is;
}
Vector operator - (const Point &a,const Point &b){return (Vector){a.x-b.x,a.y-b.y};}//两点相减得到一个向量
double Length(Vector x){return sqrt(x.x*x.x+x.y*x.y);}//返回长度
double Cross(Vector x,Vector y){return x.x*y.y-x.y*y.x;}//叉乘
const double eps=1e-8;
int judge(double k){if(fabs(k)<eps)return 0;return k>0?1:-1;}//防止精度问题，判断浮点数正负
Point stk[N];
int top,n;
int main(void)
{
n=gi;
for(int i=1;i<=n;++i)cin>>p[i];
sort(p+1,p+n+1,[&](Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;});
for(int i=1;i<=n;++i)
{
while(top>1&&judge(Cross(stk[top]-stk[top-1],p[i]-stk[top-1]))<0)--top;
stk[++top]=p[i];
}
for(int i=n;i>=1;--i)
{
while(judge(Cross(stk[top]-stk[top-1],p[i]-stk[top-1]))<0)--top;
stk[++top]=p[i];
}
double ans=0;
stk[0]=stk[top];//首尾相连，方便计算
for(int i=1;i<=top;++i)ans+=Length(stk[i]-stk[i-1]);
printf("%.2lf",ans);
return 0;
}
原文：https://www.cnblogs.com/LLCSBlog/p/11178482.html