在考研机试中，有的时候会考到一些基础的计算几何知识，其中包括点积、叉积、凸包等内容。

首先在二维坐标下介绍一些定义：

点：A (x1，y1),  B (x2，y2)
向量：向量AB= (x2 - x1 , y2 - y1 ) = (x ,  y)
向量的模 |AB| = sqrt (x * x + y * y)

点积

向量的点积： 结果为 x1*x2 + y1*y2。
点积的结果是一个数值。

点积的集合意义：我们以向量 a 向向量 b 做垂线，则 | a | * cos(a,b)为 a 在向量 b 上的投影，即点积是一个向量在另一个向量上的投影乘以另一个向量，且满足交换律。

应用：可以根据集合意义求两向量的夹角，cos(a,b) = (向量a * 向量b) / (| a | * | b |) =  x1*x2 + y1*y2 / (| a | * | b |)

叉积

向量的叉积： 结果为 x1*y2-x2*y1
叉积的结果也是一个向量，是垂直于向量a，b所形成的平面，如果看成三维坐标的话是在 z 轴上，上面结果是它的模。

方向判定：右手定则，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉积的方向）

叉积的集合意义：

1、其结果是a和b为相邻边形成平行四边形的面积。
2、结果有正有负，有sin（a，b）可知和其夹角有关，夹角大于180°为负值。
3、叉积不满足交换律

应用：

1、通过结果的正负判断两矢量之间的顺逆时针关系
若 a x b > 0表示a在b的顺时针方向上
若 a x b < 0表示a在b的逆时针方向上
若 a x b == 0表示a在b共线，但不确定方向是否相同
2、判断折线拐向，可转化为判断第三点在前两的形成直线的顺逆时针方向，然后判断拐向。
3、判断一个点在一条直线的那一侧，同样上面的方法。
4、判断点是否在线段上，可利用叉乘首先判断是否共线，然后在判断是否在其上。
5、判断两条直线是否想交（跨立实验）
根据判断点在直线那一侧我们可以判断一个线段的上的两点分别在另一个线段的两侧，当然这是不够的，因为我们画图发现这样只能够让直线想交，而不是线段，所以我们还要对另一条线段也进行相同的判断就ok。

凸包

凸多边形

凸多边形是指所有内角大小都在[0, π]范围内的 简单多边形 。

凸包

在平面上能包含所有给定点的最小凸多边形叫做凸包。

其定义为：

对于给定集合X，所有包含X的凸集的交集S被称为X的凸包 。
实际上可以理解为用一个橡皮筋包含住所有给定点的形态。
凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点，它的周长一定不是最小，如下图。根据三角不等式，凸多边形在周长上一定是最优的。

凸包的求法

我们这里不详细讲解与证明凸包算法的原理，其本质就是极角坐标排序，我们主要是告诉大家如何使用凸包算法的模板。

凸包面积
题目描述：
麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最...

题目练习

DreamJudge 1160 球的半径和体积
DreamJudge 1183 Freckles
DreamJudge 1211 矩形相交
DreamJudge 1596 球形空间产生器
DreamJudge 1615 多边形的面积
DreamJudge 1620 放牧
DreamJudge 1621 玩具