根神入门之向量入门

· · 个人记录

更好的阅读体验？

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

定义

首先介绍一下点：

点可以用二维坐标 (x, y) 表示，可以用结构体 Point 存储。

struct Point{
    int x, y;
};

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

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

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

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

typedef Point Vector;

四则运算

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

例如此图，\vec{u} = (3,1), \vec{v} = (1,4), \vec{w} = (3,-2)，那么 \vec{a} =\vec{u} + \vec{v} = (3+1, 1+4) = (4,5)，\vec{b} =\vec{u} + \vec{w} = (3+3, 1-2) = (6,-1)。

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

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

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

如果你要求 \vec{w} = \vec{u} - \vec{v}，那么先让 \vec{u} 和 \vec{v} 起点重合，\vec{w} 就是从 \vec{v} 的终点连向 \vec{u} 的终点的一个向量。

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

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

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

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

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

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

点积与叉积

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

点积

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

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

如图，\boldsymbol{u} \cdot \boldsymbol{v} = AB \times AC \times \cos\theta = AD \times AC。于是我们得出了他的几何意义：\boldsymbol{u} \cdot \boldsymbol{v} 就是 \boldsymbol{u} 在 \boldsymbol{v} 上的投影长度乘以 \boldsymbol{v} 的模长。

这个夹角 \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*}

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

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

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

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

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

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

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

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

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

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

所以可以看出，叉积没有交换律。叉积是有顺序的。\boldsymbol{u} \times \boldsymbol{v} 和 \boldsymbol{v} \times \boldsymbol{u} 互为相反数。

他的几何意义：以向量 \boldsymbol{u} 和 \boldsymbol{v} 作为边形成的平行四边形的面积就是 \boldsymbol{u} \times \boldsymbol{v} 的绝对值。

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

直线

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

  1. 用直线上的两个点的坐标表示，因为两点确定一条直线
  2. y = kx + b$ / $ax + by + c = 0
  3. 根据一个点和倾斜角确定
  4. 点向式：P = P_0 + vt：P_0 为一个点，v 是一个向量。
struct Line{
    Point p1, p2; //两点确定一条直线
};

叉积的应用

判断点 x 在直线 (p_1,p_2)（其实是向量）的左边、右边或是点就在直线上。

这个可以有两种算法：

  1. 构造向量 \vec{p_1x} 和向量 \vec{p_2x}，然后用叉积的正负来判断方向。
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 重合
}
  1. 构造向量 \vec{p_1x}，求 \vec{p_1p_2} \times \vec{p_1x}，然后用叉积的正负判断方向。个人觉得这种方法更加直观。
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 类型，所以判断相不相等的时候肯定是会有一些误差的。我们要规避掉。我们可以设置一个极小值 eps 来减小这个误差。

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


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;
    }
    ...
}

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

二维凸包的定义

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

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

我们来介绍一个 O(n\log n) 的算法求一些点的二维凸包。

Andrew 算法求二维凸包

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

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

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

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

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

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

注意要持续检测！

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

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

看题目要求。

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

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

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

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

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

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

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

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

当 len > 1 时，弹出栈顶元素。

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

例题：

二维凸包模板