向量

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

何謂向量

向量（Vector）表示特定的長度和方向，簡單來說，你可以想成向量是一個箭頭。例如物理上的力、位移都算是向量。

向量可以是任何維度的，也就是說，有二維向量、也有三維向量、一維向量……，然後一個

$n$ 維向量可以用

$n$ 個數字來表示，第

$i$ 個數字表示要往第

$i$ 個維度的正向走多少距離（如果是負數，就是往負向走），而這個向量可以被看成是一個從起點指向終點的箭頭，舉例來說：

這是一個二維向量，它表示向著

$x$ 軸正向走

$2$，並向著

$y$ 軸正向走

$3$，所以如果從原點開始走，會走到點

$(2,3)$。

（詳細的數學定義有興趣可以自己去查。）

向量有幾種表示方式，有把數字放在矩陣裡，寫成

$\left[\begin{array}{c}{v}_1\\ v_2\\ ...\end{array}\right]$ 或

$\left[\begin{array}{ccc}v1& v2& ...\end{array}\right]$ 這種形式的，也有放在多元組裡，寫成

$(v_1,v_2,...)$ 的，如果沒有特別需要用到矩陣，通常會用多元組來表示。

一個

$n$ 維向量

$(v_1,v_2,...,v_n)$ 的長度可以用類似畢式定理來算：

$$\sqrt{\sum _{i=1}^n{v}_i^2}$$

長度為

$0$ 的向量稱為「零向量」，零向量可以是任意方向的。為了方便，除非特別註明，接下來提到的向量都不包含零向量。

基本符號：

• $\overrightarrow{AB}$，也可以寫成
  $B-A$，
  $A$、
  $B$ 是點，表示由
  $A$ 指向
  $B$ 的向量。（注意向量沒有特定的起終點，只能規定它的方向和長度）
• $\overrightarrow{A}$，
  $A$ 是點，等同於
  $\overrightarrow{OA}$，
  $O$ 是原點。
• $|\overrightarrow{v}|$，向量
  $\overrightarrow{v}$ 的長度。

基本運算

可以發現到，由原點指向某個點

$(x,y)$ 的向量，就是

$(x,y)$，所以也可以把點想成是向量、也可以把向量想成是點，這會有助於理解接下來的東西。

加減

兩個向量可以相加得到新的向量，就把所有維度的分量分別相加就好：

$$(u_1,u_2,u_3,...)+(v_1,v_2,v_3,...)=(u_1+v_1,u_2+v_2,u_3+v_3,...)$$

例如，

$(2,3)+(3,1)=(5,4)$：

兩個向量相加等同於兩個力的合力，你也可以發現它會滿足平行四邊形法則。

至於減法，就移項一下就可以暸解要怎麼做了，也可以想成是一個向量加上另一個向量的反向，或者是把兩個向量想成點，

$\overrightarrow{A}-\overrightarrow{B}=A-B$，也就是一個從點

$B$ 指向點

$A$ 的向量，例如，

$(2,3)-(3,1)=(-1,2)$：

純量乘法

沒有方向的量稱為純量，像是

$1$、

$\frac{1}{2}$、

$\pi$ 這些數字都是純量。向量可以乘上一個純量，得到一個新的向量，也就是將這個向量的長度乘上某一個數字，得到一個新的向量，這個動作非常簡單，就把每個維度的分量都乘上這個純量就好：

$$i(v_1,v_2,v_3,...)=(i{v}_1,i{v}_2,i{v}_3,...)$$

例如，

$2\times (2,3)=(4,6)$：

內積（點積）

這是向量特有的運算，兩個夾角是

$\theta$ 的

$n$ 維向量

$\overrightarrow{u}=(u_1,u_2,...,u_n)$ 和

$\overrightarrow{v}=(v_1,v_2,...,v_n)$ 的內積記作

$\overrightarrow{u}\cdot \overrightarrow{v}$，結果是一個純量：

$$\overrightarrow{u}\cdot \overrightarrow{v}=|\overrightarrow{u}||\overrightarrow{v}|\cos \theta =\sum _{i=1}^n{u}_i{v}_i$$

其實就是把每一個維度的分量長相乘後相加，例如二維向量

$(x_1,y_1)\cdot (x_2,y_2)=x_1{x}_2+y_1{y}_2$。意義是作一個

$\overrightarrow{u}$ 在

$\overrightarrow{v}$ 上垂直投影的向量，然後將這個向量的長和

$\overrightarrow{v}$ 的長相乘。

（內積是

$|\overrightarrow{u}|\cos \theta$ 再乘上

$|\overrightarrow{v}|$，你想要

$\theta$ 是裡面那個角還是外面那個角都沒差，畢竟

$\cos \theta =\cos (2\pi -\theta )$。如果夾角超過直角，那麼投影會在另一邊，此時

$|\overrightarrow{u}|\cos \theta$ 會是負數。）

$\overrightarrow{F}\cdot \overrightarrow{S}$ 在力學上的意義是，對一個物體作一個力

$\overrightarrow{F}$，而物體的位移是

$\overrightarrow{S}$，則

$\overrightarrow{F}\cdot \overrightarrow{S}$ 是

$\overrightarrow{F}$ 對這個物體所作的功。

既然內積只是多維版本的乘法，那內積也和乘法一樣，滿足交換律、分配律與結合律。

接下來針對兩個向量的夾角

$\theta$ 大小來討論內積的結果為何（以下會同時寫上角度和弧度）：

• $\theta ={90}^{\circ }=\frac{1}{2}\pi$
  顯而易見地，如果作用在一個物體上的力和物體位移方向垂直，那麼這個力對這個物體不作功，且
  $\cos {90}^{\circ }=\cos \frac{1}{2}\pi$ 也確實為
  $0$，因此我們知道，兩個垂直的向量內積是
  $0$。
• $\theta =0^{\circ }=0$
  如果作用在一個物體上的力和物體位移方向相同，那麼這個力作的功等同於力的大小乘上位移距離，同樣
  $\cos 0^{\circ }=\cos 0$ 也是
  $1$，因此兩個方向相同的向量
  $\overrightarrow{u}$、
  $\overrightarrow{v}$ 的內積是
  $|\overrightarrow{u}||\overrightarrow{v}|$。
• $\theta ={180}^{\circ }=\pi$
  如果作用在一個物體上的力和物體位移方向相反，那麼這個力作的會是負功，且這個負功的大小等於力的大小乘上位移距離，同樣
  $\cos {180}^{\circ }=\cos \pi$ 是
  $-1$，因此兩個方向相反的向量
  $\overrightarrow{u}$、
  $\overrightarrow{v}$ 內積是
  $-|\overrightarrow{u}||\overrightarrow{v}|$。
• $0^{\circ }=0<\theta <{90}^{\circ }=\frac{1}{2}\pi$
  也就是兩個向量方向在同一邊的時候，顯然如果作用在一個物體上的力和物體位移方向在同一邊，那麼這個力作的會是正功，同樣
  $\cos \theta$ 的範圍會是
  $(0,1)$，因此兩個夾角是
  $\theta$、方向在同一邊的向量
  $\overrightarrow{u}$、
  $\overrightarrow{v}$ 內積會是一個正數且
  $0<\overrightarrow{u}\cdot \overrightarrow{v}<|\overrightarrow{u}||\overrightarrow{v}|$。
• ${90}^{\circ }=\frac{1}{2}\pi <\theta <{180}^{\circ }=\pi$
  也就是兩個向量方向在不同邊的時候，如果作用在一個物體上的力和物體位移方向在不同邊，那麼這個力作的會是負功，同樣
  $\cos \theta$ 的範圍會是
  $(-1,0)$，因此兩個夾角是
  $\theta$、方向在不同邊的向量
  $\overrightarrow{u}$、
  $\overrightarrow{v}$ 內積會是一個負數且
  $-|\overrightarrow{u}||\overrightarrow{v}|<\overrightarrow{u}\cdot \overrightarrow{v}<0$。

兩向量在不同夾角時的內積：

兩個長度為

$1$ 的向量在不同夾角時的內積（

$x$ 軸為夾角（弧度）、

$y$ 軸為內積）：

內積常被用來判斷兩個向量是否垂直，也可以用來判斷兩個向量的方向是否在同一邊、是否相同或者相反。

外積（叉積）

向量特有的運算，在定義上，它只能用在三維，兩個三維向量

$\overrightarrow{u}=(x_1,y_1,z_1)$ 和

$\overrightarrow{v}=(x_2,y_2,z_2)$ 的外積記作

$\overrightarrow{u}\times \overrightarrow{v}$，是一個新的二維向量 （

$x_3,y_3,z_3$）：

$$\overrightarrow{u}\times \overrightarrow{v}=\left|\begin{array}{ccc}\mathbf{i}& \mathbf{j}& \mathbf{k}\\ x_1& y_1& z_1\\ x_2& y_2& z_2\end{array}\right|=(y_1{z}_2-z_1{y}_2)\mathbf{\text{i}}-(x_1{z}_2-z_1{x}_2)\mathbf{\text{j}}+(x_1{y}_2-y_1{x}_2)\mathbf{\text{k}}$$

其中，

$\mathbf{i}$、

$\mathbf{j}$、

$\mathbf{k}$ 是三個維度的「基向量」，有興趣可以自己查。外積得到的向量會垂直於

$\overrightarrow{u}$ 和

$\overrightarrow{v}$ 構成的平面，且當

$\overrightarrow{u}$ 和

$\overrightarrow{v}$ 的夾角是

$\theta$，外積得到的向量長度是：

$$||\overrightarrow{u}||\overrightarrow{v}|\sin \theta |$$

它的長度等同於兩個向量所夾的平行四邊形面積。

至於它的方向，會依據右手定則，右手食指指向

$\overrightarrow{u}$，中指指向

$\overrightarrow{v}$，大姆指的方向就會是

$\overrightarrow{u}\times \overrightarrow{v}$ 的方向。

以上看不懂都沒關係，因為它的三維定義不重要。二維向量的外積在比賽上比較常用，但剛剛不是說只能用在三維？你會發現把第三維全部代

$0$，就會變成：

$$\overrightarrow{u}\times \overrightarrow{v}=(x_1{y}_2-y_1{x}_2)\mathbf{\text{k}}$$

$\mathbf{\text{k}}$ 的部分是第三維的基向量，在一般的直角座標系，它是

$(0,0,1)$，長度是

$1$，然後我們不要管它，把二維外積定義為三維外積的長度（純量），如果三維外積的結果向量向上，那二維外積是正的，否則就是負的，可以得出：

$$\overrightarrow{u}\times \overrightarrow{v}=\left|\begin{array}{cc}{x}_1& y_1\\ x_2& y_2\end{array}\right|=x_1{y}_2-y_1{x}_2=|\overrightarrow{u}||\overrightarrow{v}|\sin \theta$$

相同地，這個值等同於兩個向量所夾的平行四邊形面積，但它是「有向」的，如果

$\overrightarrow{u}$ 轉向

$\overrightarrow{v}$ 是逆時針，那會是正的，反之就會是負的（這邊的轉指往較近那邊轉），至於夾角

$\theta$ 是指

$\overrightarrow{u}$ 往逆時針轉到

$\overrightarrow{v}$ 的角度。

外積不滿足交換律，也就是說

$\overrightarrow{u}\times \overrightarrow{v}\ne \overrightarrow{v}\times \overrightarrow{u}$，但它滿足「負交換律」，也就是

$\overrightarrow{u}\times \overrightarrow{v}=-(\overrightarrow{v}\times \overrightarrow{u})$，因為：

$$\begin{gathered} (x_1,y_1)\times (x_2,y_2)=x_1{y}_2-x_2{y}_1 \\ =-(x_2{y}_1-x_1{y}_2)=-(x_2,y_2)\times (x_1,y_1) \end{gathered}$$

外積不滿足結合律，但滿足分配律。

接下來我們針對各種夾角

$\theta$ 討論它的值：

• $\theta ={90}^{\circ }=\frac{1}{2}\pi$
  這樣兩個向量會夾一個長方形，且
  $\sin {90}^{\circ }=\sin \frac{1}{2}\pi =1$，因此兩個夾角為直角的向量
  $\overrightarrow{u}$、
  $\overrightarrow{v}$ 外積為
  $|\overrightarrow{u}||\overrightarrow{v}|$。
• $\theta ={270}^{\circ }=\frac{3}{2}\pi$
  這樣兩個向量會夾一個長方形，且
  $\sin {270}^{\circ }=\sin \frac{3}{2}\pi =-1$，但
  $\overrightarrow{u}$ 轉向
  $\overrightarrow{v}$ 是順時針，因此
  $\overrightarrow{u}\times \overrightarrow{v}=-|\overrightarrow{u}||\overrightarrow{v}|$。
• $\theta =0^{\circ }=0$
  兩個向量同向，那麼它們夾的平行四邊形面積為
  $0$，且
  $\sin 0^{\circ }=\sin 0=0$，因此此時外積值為
  $0$。
• $\theta ={180}^{\circ }=\pi$
  兩個向量反向，此時它們夾的平行四邊形面積也為
  $0$，且
  $\sin {180}^{\circ }=\sin \pi =0$，因此此時外積值為
  $0$。
• $0^{\circ }=0<\theta <{180}^{\circ }=\pi$
  
  $\overrightarrow{u}$ 往
  $\overrightarrow{v}$ 轉是逆時針，且
  $\sin \theta \in (0,1]$，則
  $\overrightarrow{u}\times \overrightarrow{v}>0$。除非
  $\theta ={90}^{\circ }=\frac{1}{2}\pi$，不然
  $\sin \theta <1$，則
  $0<\overrightarrow{u}\times \overrightarrow{v}<|\overrightarrow{u}||\overrightarrow{v}|$。
• ${180}^{\circ }=\pi <\theta <{360}^{\circ }=2\pi$
  
  $\overrightarrow{u}$ 往
  $\overrightarrow{v}$ 轉是順時針，且
  $\sin \theta \in [-1,0)$，則
  $\overrightarrow{u}\times \overrightarrow{v}<0$。除非
  $\theta ={270}^{\circ }=\frac{1}{2}\pi$，不然
  $\sin \theta >-1$，則
  $-|\overrightarrow{u}||\overrightarrow{v}|<\overrightarrow{u}\times \overrightarrow{v}<0$。

兩向量在不同夾角時的外積：

兩個長度為

$1$ 的向量在不同夾角時的外積（

$x$ 軸為夾角（弧度）、

$y$ 軸為外積）：

實作

有些人會把向量（或點）做成一個類別，不過我自己是習慣直接用 pair，然後再做運算子重載。

#define F first
#define S second
#define mp make_pair

template<typename T>
pair<T, T> operator+(pair<T, T> a, pair<T, T> b){
    return mp(a.F + b.F, a.S + b.S);
}

template<typename T>
pair<T, T> operator-(pair<T, T> a, pair<T, T> b){
    return mp(a.F - b.F, a.S - b.S);
}

template<typename T> //純量乘法
pair<T, T> operator*(pair<T, T> a, T i){
    return mp(i * a.F, i * a.S);
}

template<typename T> //純量除法
pair<T, T> operator/(pair<T, T> a, T i){
    return mp(a.F / i, a.S / i);
}

template<typename T> //內積
pair<T, T> dot(pair<T, T> a, pair<T, T> b){
    return mp(a.F * b.F, a.S * b.S);
}

template<typename T> //外積
T cross(pair<T, T> a, pair<T, T> b){
    return mp(a.F * b.S, a.S * b.F);
}

template<typename T> //向量長的平方
T vabs2(pair<T, T> a){
    return a.F * a.F + a.S * a.S;
}