一点点计算几何：向量的入门

~~学好了数学，你就会成为根神！数学乃万物之根，掌握了数学就掌握了一切！~~

定义

首先介绍一下点：

点可以用二维坐标表示，可以用结构体 Point 存储。

1
2
3

struct Point{
    int x, y;
};

有大小并且有方向的量叫向量。我们可以把他看作连接了两个点。

同时，为了方便，我们可以记录一个坐标，就相当于是从指向。

如图，一个从点连向的向量可以看作从连向的向量。所以为了方便，我们可以直接用表示这个向量。因为这两个向量在平面上其实是相等的。

于是为了方便写代码，我们可以执行这个操作：

1	typedef Point Vector;

四则运算

加法运算

点加点显然是没有意义的。而向量加向量是有意义的。就相当于是把后一个向量的起点给放在前一个向量的终点上，然后求后一个向量的终点的坐标。

例如此图，，那么，。

那么就相当于是把两个向量的横坐标加起来当作新的横坐标，两个向量的纵坐标当作新的纵坐标。

1
2
3

Vector operator + (const Vector &a, const Vector &b){
    return {a.x + b.x, a.y + b.y};
}

减法运算

几何意义上的向量的减法运算就是：

如果你要求，那么先让和起点重合，就是从的终点连向的终点的一个向量。

代数意义上，的横坐标就是的横坐标减去的横坐标，的纵坐标就是的纵坐标减去的纵坐标。这个减法和普通的减法一样，都有顺序！！

1
2
3

Vector operator - (const Vector &a, const Vector &b){
    return {a.x - b.x, a.y - b.y};
}

数乘运算

一个向量乘以一个数就是相当于是把这个向量放大到他的倍。

1
2
3

Vector operator * (const Vector &a, const int &b){
    return {a.x * b, a.y * b};
}

除法运算

一个向量除以一个数就是相当于是把这个向量缩小到他的。（实际运算的时候要根据精度将点的类型改成 double 或 long double 等等）

1
2
3

Vector operator / (const Vector &a, const int &b){
    return {a.x / b, a.y / b};
}

点积与叉积

点积和叉积都是向量乘以向量，但是它们不同。这两个名字其实是根据两个不同的 “乘法符号” 命名的，点积就是，叉积就是。非常的生动形象啊。

点积

点积的结果是一个数值。运算是这样的：

$\boldsymbol{a} \cdot \boldsymbol{b} = |\boldsymbol{a}| \times |\boldsymbol{b}| \times \cos \theta$

如图，。于是我们得出了他的几何意义：就是在上的投影长度乘以的模长。

这个夹角是两个向量的两个角里面最小的那一个。

而有一种更简单的算法：

$\boldsymbol{u} \cdot \boldsymbol{v} = \boldsymbol{u}.x \times \boldsymbol{v}.x + \boldsymbol{u}.y \times \boldsymbol{v}.y$

考虑证明：

$\begin{align*}%不会产生编号 &\boldsymbol{u}.x \times \boldsymbol{v}.x + \boldsymbol{u}.y \times \boldsymbol{v}.y\\ &= (|\boldsymbol{u}| \times \cos \theta_1) (|\boldsymbol{v}| \times cos\theta_2) + (|\boldsymbol{u}| \times \sin\theta_1)(|\boldsymbol{v}| \times \sin\theta_2)\\ &= (|\boldsymbol{u}||\boldsymbol{v}|\cos\theta_1\cos\theta_2) + (|\boldsymbol{u}||\boldsymbol{v}|\sin\theta_1\sin\theta_2) \\ &= |\boldsymbol{u}||\boldsymbol{v}|(\cos\theta_1\cos\theta_2 + \sin\theta_1\sin\theta_2)\\ &= |\boldsymbol{u}||\boldsymbol{v}|\cos(\theta_1-\theta_2)\\ &= |\boldsymbol{u}||\boldsymbol{v}|\cos\theta \end{align*}$

根据这个东西我们可以看出来点积其实是有交换律的。

于是我们可以得出一些性质：

若，那么与的夹角为锐角。
若，那么与的夹角为钝角。
若，那么与的夹角为直角。

（其实看可以直接判断出来）

1
2
3

int Dot(Point u, Point v){
    return u.x*v.x + u.y*v.y;
}

点积的应用

最直观地、可以求两个向量的夹角。

double Len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}
double Angle(Vector u, Vector v){
    return acos(Dot(u, v)/Len(u)/Len(v));
}

叉积

叉积的结果是也一个数值。运算是这样的：

$\boldsymbol{u} \times \boldsymbol{v} = |\boldsymbol{u}| \times |\boldsymbol{v}| \times \sin \theta$

和上面的点积形式比较像，就是把改为了。

但是注意：这里的是 向量 u 逆时针旋转到向量 v 所经过的角度。

所以，叉积有正有负。即：

当在的逆时针方向时（左侧），那么。
当在的顺时针方向时（右侧），那么。
当和的方向相同或相反时（共线），那么。

这个也可以从的定义中看出来。

而叉积也有一个很好算的神奇公式：

$\boldsymbol{u} \times \boldsymbol{v} = \boldsymbol{u}.x \times \boldsymbol{v}.y - \boldsymbol{u}.y \times \boldsymbol{v}.x$

所以可以看出，叉积没有交换律。叉积是有顺序的。和互为相反数。

他的几何意义：以向量和作为边形成的平行四边形的面积就是的绝对值。

1
2
3

int Cross(Point u, Point v){
    return u.x*v.y - u.y*v.x;
}

直线

众所周知，直线可以用以下几个方法表示：

用直线上的两个点的坐标表示，因为两点确定一条直线
/
根据一个点和倾斜角确定
点向式：：为一个点，是一个向量。

1
2
3

struct Line{
    Point p1, p2; //两点确定一条直线
};

叉积的应用

点和直线的位置关系

判断点在直线（其实是向量）的左边、右边或是点就在直线上。

这个可以有两种算法：

构造向量和向量，然后用叉积的正负来判断方向。

int Relation(Point p, Line l){
    int res = Cross(p-l.p1, p-l.p2);
    if(res < 0) return 1; // p 在 l 的左侧
    if(res > 0) return 2; // p 在 l 的右侧
    return 0; // p 与 l 重合
}

构造向量，求，然后用叉积的正负判断方向。个人觉得这种方法更加直观。

int Relation(Point p, Line l){
    int res = Cross(l.p2 - l.p1, p - l.p1);
    if(res > 0) return 1; // p 在 l 的左侧
    if(res < 0) return 2; // p 在 l 的右侧
    return 0; // p 与 l 重合
}

例题：

神秘大三角

Tips

在向量运算的过程中，因为用的是 double 类型，所以判断相不相等的时候肯定是会有一些误差的。我们要规避掉。我们可以设置一个极小值来减小这个误差。

可读性最高的方法是重载运算符。这里使用了重新写一个函数的方式。


const double eps = 1e-9;
int cmp(double x){
    if(fabs(x) < eps) return 0; // x == 0
    else if(x < eps) return -1; // x < 0
    return 1; // x > 0
}
bool operator < (const)
struct Point{
    ...
    bool operator == (const Point &b){
        if(cmp(b.p2 - p2) == 0 && cmp(b.p1 - p1) == 0) return 1;
        return 0;
    }
    ...
}

于是入门就先到这里，我们来讲二维凸包。（后面可能会在入门里面再添加内容）

二维凸包的定义

二维凸包就相当于，通俗的讲，你在平面上有一些大头针，你有一个橡皮筋，你用一个橡皮筋把所有的这些大头针包在里面，那么这个橡皮筋的形状就可以粗略看作是这些点的凸包的形状。

上图中灰色的一个凸多边形就是这些蓝色点的凸包。它包住了所有的蓝点。

我们来介绍一个的算法求一些点的二维凸包。

Andrew 算法求二维凸包

我们首先给这些点排序：按照坐标从小到大排序，如果坐标相等，那么就按照坐标从小到大排序。

然后我们选定最左边的点（也就是），然后就可以开始造凸包了。

我们将我们遍历过的所有点压进一个栈里面，当遍历到一个新的点的时候，判断他和栈顶的两个点的位置关系，然后来判断删不删。我们依然来举例说明：

首先栈中不足个点，压入点和；

这个时候，第三个点来了，我们让他和栈顶点和次栈顶点判断一下位置关系：

具体的操作是，让栈顶的点和新点和次栈顶的点连成的直线判断位置关系。如上图，我们发现栈顶点在新点和次栈顶点做成的直线的左侧，很明显，如果不把给踢出去，那么就不是一个凸包了。我们就把这个栈 pop 一下，然后继续检测。直到符合条件或是栈中的元素小于了，那么就把新点加进来。

注意要持续检测！

另一个例子，插入点时的判断：

注意：当新点和栈顶点、次栈顶点共线时：

看题目要求。

当所有点都被遍历完了之后，我们看到了一个凸包的雏形：

注：这里的是下凸包的点的个数，也是上凸包弹出元素时的边界。这个元素必须保留在栈里面。

然后我们就可以开始再从后往前遍历一遍，来找上凸包。

找上凸包的过程其实和找下凸包的过程都是一样的，但是注意一下边界问题。

具体地说，弹出元素的操作只适用于当前栈元素大于的情况。

因为你再弹出，你就把下凸包的右端点给弹出去了。

最后，我们得到了一个栈和一个凸包：

但是，我们发现这个凸包的点（即栈）里面有两个左端点。就判一下（设栈中元素个数为）：

当时，弹出栈顶元素。

于是我们就完美的得到了这个凸包了！

例题：