写在前面

向量在计算几何中是最常用的结构，也是包含运算较多的结构

向量运算的实现

    struct point{
        double x,y;//定义构造函数会对后面的工作提供极大的便利
        point(){}

        point(double _x,double _y)x:(_x),y(_y){}  //采用运算符重载的方式实现向量的运算

        /*
        或者这样写：
        point(double a=0,double b=0){
            x=a,y=b;
        }
        */

        point operator+(point a){   //向量加法
            return point(x+a.x,y+a.y);
        }

        point operator-(point a){   //向量减法
            return point(x-a.x,y-a.y);
        }

        double operator*(point a){  //向量叉积
            return x*a.y-a.x*y;
        }

        double operator^(point a){  //向量点积
            return x*a.x+y*a.y;
        }

        point operator*(double a){ //向量乘以实数
            return point(a*x,a*y);
        }

        double len2(){             //向量模的平方
            return x*x+y*y;
        }
    };

1.一些基本概念：

1）关于一条线段

一条线段如下图所示（在二维平面上）：

那么很简单的是，我们可以直接用AB来表示这条线段，那么我们还可以用点+向量的形式来表示这条线段，如上图AB就可以表示为A+
$\overrightarrow{AB}$
=B，或者也可以表示为B+
$\overrightarrow{BA}$
=A，都是可以的。同样，对于AB上任意一点C，都满足下面这个式子：

如果存在任意C∈AB，都存在
$\exists$
（存在）p∈[0,1]，使得C=(1-p)A+pB。（p指AC：AB的比例）

证明见下图：

我们过C作CD
$\parallel$
OB交OA于D，作CE
$\parallel$
OA交OB于E，首先因为有DC
$\parallel$
OB，所以
$\triangle$
ADC
$\sim$
$\triangle$
AOB，所以有AD：DO=AC：BC=p：1-p，所以OD=(1-p)OA，同理OE=pOB，因为向量的加减满足平行四边形法则（见下方4.2），所以有
$\overrightarrow{OC}$
=
$\overrightarrow{OD}+\overrightarrow{OE}$
，最后代换一下即可得到上方的式子。

2.关于一条直线

直线一般就是利用直线上的两个点来表示，方法同上。

3.关于一个多边形

最主要的还是一个存储问题，通常我们会按顺时针或逆时针的顺序存储多边形的顶点，或者存边及其起点。

4.关于向量

几何向量就是指线性空间里既有大小又有方向的量（没错就是矢量）

1）关于向量的表示

向量其实可以理解为一条带箭头的线段，箭头代表方向，线段长度代表大小，如果给定起点A和终点B，那么这个向量就可以表示为
$\overrightarrow{AB}$
，同样也可以用小写字母
$\overrightarrow{a}$
的形式来表示。

在平面直角坐标系上，同样也可以用数对的形式来表示：A(x1,y1)，B(x2,y2)→
$\overrightarrow{AB}$
=(x2-x1,y2-y1)。

设
$\overrightarrow{a}=\overrightarrow{AB}$
，那么有向线段AB的长度叫做向量a的模，记作|a|，大小就是两点的欧几里得距离。

2）关于向量的运算

向量的运算遵循平行四边形法则（现在不懂没关系，高中物理会讲，数学也会讲）

加减法就非常形象，一张图搞定：

$\overrightarrow{OA}+\overrightarrow{OB}=\overrightarrow{OC}$
，
$\overrightarrow{OC}-\overrightarrow{OB}=\overrightarrow{BC}$
，
$\overrightarrow{OB}-\overrightarrow{OC}=\overrightarrow{CB}$

我们可以这样理解：因为OA
$\parallel$
AC，那么向量OA与OB的和就可以视为O先移动到A，再从A移动到C，所以向量OA与OB的和就是OC。其他两个式子同理。

同样可以用坐标表示出来：

加法：a+b=(x1+x2,y1+y2)，减法：a-b=(x1-x2,y1-y2)。

然后是向量去乘以（或除以）一个非零数，也很明显，就是向量的放缩，如果为负数顺带反向。图示：

向量OA乘以一个(0,1)之间的数可得到OA’，乘以一个(1,
$\infty$
)的数可得到OA”，乘以一个负数可得到OA”’。

3）向量与向量之间的一些操作

1.向量之间的夹角。

对于两个非零向量
$\overrightarrow{a},\overrightarrow{b}$
，任取一点O，作
$\overrightarrow{OA}=\overrightarrow{a}$
,
$\overrightarrow{OB}=\overrightarrow{b}$
，那么
$\angle{AOB}$
就叫向量a、b的夹角，记作<
$\overrightarrow{a},\overrightarrow{b}$
>

2.向量的点积与叉积

首先需要点预备知识：和角公式（如果不会请自行百度）

a=(x1,y1),b=(x2,y2)的点积用
$a\cdot b$
表示，
$a\cdot b=x1x2+y1y2$
。它的结果是一个标量（只有大小没有方向） .它的几何意义是向量a在向量b方向上的投影与向量b的模的乘积，即
$a\cdot b=|a|\times|b|\times cos<a,b>$
。

大概就是这个意思：

OC就是OB在OA方向上的投影，最后的结果就是OC
$\times$
OA。

小小证明一下：

由平面内两点距离公式我们可以得到
$OB=\sqrt{x1^2+y1^2},OA=\sqrt{x2^2+y2^2}$
，

令OC为OB在OA上的投影，
$\angle BOx=\beta,\angle AOx=\theta$
,

可得x1=OB*cos
$\beta$
,y1=OB*sin
$\beta$
,x2=OA*cos
$\theta$
，y2=OA*sin
$\theta$
，所以x1x2+y1y2=OA*OB*(
$cos\beta \times cos\theta +sin\beta \times sin\theta$
)

由和角公式：
$cos(\alpha-\beta)=cos\alpha \times cos\beta + sin\alpha \times sin\beta$
，可得x1x2+y1y2=OA*OB*
$cos(\beta-\theta)$
=向量OC的模*向量OA的模。证毕。

那么利用点积我们可以干什么呢？判垂直！显然，如果向量OB
$\perp$
OA，那么向量OB在向量OA上的投影的模为0，那么二者的点积就为0。

这些都可以推广到n维空间，即
$a\cdot b=\sum_{i=1}^{n}a_{i}b_{i}$

然后是向量的叉积。

三维叉积：两个向量a=(x1,y1,z1),b=(x2,y2,z2)的叉积的结果是一个向量c，记作
$c=a\times b$
。

$c=\begin{vmatrix} i & j & k\\ x_{1} & y_{1} & z_{1}\\ x_{2} & y_{2} & z_{2} \end{vmatrix}$
，其中i,j,k,分别为三个轴上的单位向量。

根据叉积的计算式，可得c的模长即为以a,b为邻边所作的平行四边形的面积，c的方向遵循右手定则（右手除大拇指外四指与a 平行，方向与a 一致，大拇指与a 垂直，然后四指转过一个小于
$\pi$
的角到达b ，此时大拇指的方向就是c 的方向）

那么二维叉积呢？我们可以将其视作z=0的时候的情况，所以叉积结果为(0,0,
$x_{1}y_{2}-x_{2}y_{1}$
)。所以我们定义二维叉积为：
$a\times b=x_{1}y_{2}-x_{2}y_{1}$
，其几何意义为：其结果大小等于以a,b为邻边所作平行四边形的有向面积（这个就不需要证了吧，手推一下就出来了），即
$a\times b=|a|\times |b|\times sin<a,b>$
，而根据叉积的结果，我们能判断a,b的方向。如下图：

由此我们也可以推出
$a\times b=-b\times a$
，
$a\times b=0\Leftrightarrow$
a,b共线。

3.向量的旋转

对于向量
$\overrightarrow{OA}$
=(x1,y1)，如果我们将其逆时针旋转
$\alpha\degree$
，那么旋转后的向量
$\overrightarrow{OA'}$
的坐标怎么表示呢？见下图：

我们令向量OA的模长为L,那么x1=
$L\times cos\theta$
,y1=
$L\times sin\theta$
,x2=
$L\times cos\beta$
,y2=
$L\times sin\beta$
。

因为
$\beta=\alpha+\theta$
，所以x2=
$L\times(cos\alpha\times cos\theta-sin\alpha\times sin\theta)$
，展开可得
$x_{2}=x_{1}\times cos\alpha-y_{1}\times sin\alpha$
，y2同理。

有了上面这些东西，我们就可以得到一些奇奇怪怪的东西了

1.三角形面积公式：

如果你还在想海伦公式这种东西的话，emmm，你没救了。

我们可以利用叉积直接得到二倍三角形的面积=|
$\overrightarrow{AB}\times\overrightarrow{AC}$
|=|
$\overrightarrow{BA}\times\overrightarrow{BC}$
|=|
$\overrightarrow{CA}\times\overrightarrow{CB}$
|。

2.判断P是否在线段AB上：

直接看向量PA的大小+向量PB的大小（均取绝对值）是否等于向量AB的大小。

3.判断P是否在直线AB上：

直接看
$\overrightarrow{PA}\times\overrightarrow{PB}$
的结果是否为0即可。

4.判断连续两条线段AB,BC的拐向（求凸包的时候就是靠这个判断）：

利用叉积判断，
$\overrightarrow{AB}\times\overrightarrow{BC}$
>0则逆时针拐弯。

5.求
$\angle AOB$
的种类：

利用点积判断
$\overrightarrow{OA}\cdot\overrightarrow{OB}=0\Leftrightarrow$
直角，
$\overrightarrow{OA}\cdot\overrightarrow{OB}>0\Leftrightarrow$
锐角，
$\overrightarrow{OA}\cdot\overrightarrow{OB}<0\Leftrightarrow$
钝角。

6.求P到线段AB的最短距离：

分两种情况讨论：1.
$\angle BAP, \angle ABP$
中有一个为钝角，则最短距离为min(|PA|,|PB|)

否则最短距离为三角形ABP底边AB的高=
$\frac{|\overrightarrow{PA}\times\overrightarrow{PB}|}{|\overrightarrow{AB}|}$
.。

7.判断线段AB,CD是否相交：

判断 B A, 是否在CD两边，以及 D C, 是否在 AB 两边，还要注意共线的特殊情况：若 AB ，CD不共线，则判断：
$(\overrightarrow{CD}\times\overrightarrow{CA})\times(\overrightarrow{CD}\times\overrightarrow{CB}) \leq 0$
且
$(\overrightarrow{AB}\times\overrightarrow{AC})\times(\overrightarrow{AB}\times\overrightarrow{AD}) \leq 0$
，否则判断AB是否至少一个点在线段CD上，类似下图：

8.求两条直线（线段）的交点（假设两点不共线）

1.代数方法：就是初中教的两解析式求解，非常。。。。。好想，但信息学基本不用。。。

2.几何方法：令S1=
$\overrightarrow{AC}\times\overrightarrow{AD}$
,S2=
$\overrightarrow{BD}\times\overrightarrow{BC}$
,P=A+
$\frac{\overrightarrow{AB}\times S1}{S1+S2}$
，图示如下：

如图，三角形ACD的面积即为S1，三角形BCD的面积即为S2，那么PA:AB=S1：S1+S2（共边定理），然后就可以得到上面那个式子了。

这里贴道小例题：POJ2318 TOYS

https://blog.csdn.net/g21glf/article/details/80907277

大概就是这些了吧

原文链接：https://blog.csdn.net/g21glf/article/details/80904435