# 計算幾何 - 課前預習

## 座標與向量

座標
- 極座標
- 二維平面座標

    typedef pair<double, double> pdd; // 依據題目要求可用 double / int

向量
- 有向線段（向：方向、量：長度）
- 純量：只有大小、沒有方向的量
- $\overrightarrow{AB}$：由 A 點起始指向 B 點的向量
- 可以任意平移
- 向量長度（加絕對值表示）：兩點的歐基里德距離
$\vert\overrightarrow{AB}\vert=\sqrt{(x_1-x_2)^2 +(y_1-y_2)^2}$

向量運算
1. 向量加法 $\overrightarrow{a}+\overrightarrow{b}$
- 頭尾相連：$\overrightarrow{AB}+\overrightarrow{BC}=\overrightarrow{AC}$
- 在圖上可以用三角形法或平行四邊形法
- 代數運算：
$\overrightarrow{a}(x_1,y_1)$, $\overrightarrow{b}(x_2,y_2)$, $\overrightarrow{c}(x_3,y_3)$
$\overrightarrow{a}+\overrightarrow{b}=\overrightarrow{c}$
$\Rightarrow x_1 + x_2 = x_3$
$\Rightarrow y_1 + y_2 = y_3$
2. 向量減法 $\overrightarrow{a}-\overrightarrow{b}$
- 負向量 = 相反向量：$-\overrightarrow{AB}=\overrightarrow{BA}$
- 向量相減即加上一個相反向量：$\overrightarrow{AB}-\overrightarrow{CD}=\overrightarrow{AB}+\overrightarrow{DC}$
3. 向量係數積 $k\overrightarrow{a}$
- 幾何意義：將 $\overrightarrow{a}$ 縮放 $k$ 倍
- 計算方式：$k(x,y) = (kx,ky)$
4. 向量內積 $\overrightarrow{a} \cdot \overrightarrow{b}$
- 表示兩個向量在「同一方向」的程度。
- 兩個向量的內積（點積）以「`⋅`」表示。
- 運算結果為一個**純量**（scalar）。
- 計算方式：
- $\overrightarrow{a} \cdot \overrightarrow{b}=\vert\overrightarrow{a}\vert\vert\overrightarrow{b}\vert\cos\theta$ 其中 $\theta$ 為兩向量夾角
- [座標化形式](https://slides.com/peienwu1216/deck#/1/12)：$(x_1,y_1) \cdot (x_2,y_2) = x_1x_2+y_1y_2$
- 正定性：向量與自身的內積為其長度平方：$|\overrightarrow{a}|^2 =\overrightarrow{a} \cdot \overrightarrow{a}$
- 內積判斷角度關係：
- 運用餘弦的性質
- $\overrightarrow{a} \cdot \overrightarrow{b}>0$ 則 $0^{\circ}\leq\theta<90^{\circ}$ 銳角
- $\overrightarrow{a} \cdot \overrightarrow{b}=0$ 則 $\theta=90^{\circ}$ 垂直
- $\overrightarrow{a} \cdot \overrightarrow{b}<0$ 則 $90^{\circ}<\theta\leq180^{\circ}$ 鈍角

5. 向量外積 $\overrightarrow{a} \times \overrightarrow{b}$
- 三維空間中代表兩個向量的公垂向量
- 兩個向量的外積（叉積）以「`×`」表示。
- 三維運算結果為一個**向量**。
- 計算方式：
- $\overrightarrow{a} \times \overrightarrow{b} = |\overrightarrow{a}||\overrightarrow{b}|\sin\theta\,\overrightarrow{n}$
其中 $\theta$ 為兩向量夾角，$\overrightarrow{n}$ 是依**右手定則**決定方向的單位向量。
- 座標化形式 (二維)：
若 $\overrightarrow{a}=(x_a,y_a)$，$\overrightarrow{b}=(x_b,y_b)$，則外積為
$\overrightarrow{a} \times \overrightarrow{b} = x_ay_b - x_by_a$
（結果為**純量**）

- 特性：
- **三度空間**中外積為向量，且垂直於 $\overrightarrow{a}$ 和 $\overrightarrow{b}$ 張成的平面。
- **二度空間**外積的意義是「兩向量張成的平行四邊形的有向面積」。

- 外積判斷向量關係：
- $\overrightarrow{a} \times \overrightarrow{b} > 0$：從 $\overrightarrow{a}$ 逆時針旋轉到 $\overrightarrow{b}$。
- $\overrightarrow{a} \times \overrightarrow{b} = 0$：兩向量平行（共線）。
- $\overrightarrow{a} \times \overrightarrow{b} < 0$：從 $\overrightarrow{a}$ 順時針旋轉到 $\overrightarrow{b}$。
6. 內積 vs 外積
- 向量內積（Dot Product）
- 判斷向量是否垂直
- 結果為純量
- 向量外積（Cross Product）
- 判斷向量是否平行
- 結果為向量（今天都當純量來用）
- 判斷向量夾角方向 （順時針或是逆時針）
- 可用來計算面積
7. 向量實作
- 座標表示法 $A(x,y)$，做法跟點一樣，代表向量 $\overrightarrow{OA}$

        typedef pair<double, double> pdd; // 依據題目要求可用 double / int

- 運算子 (用多載實現)

        #define X first
        #define Y second
        #define eps 1e-12
        // #define double long long
        typedef pair<double, double> pdd;
        
        pdd operator+(pdd a, pdd b) 
        { return pdd(a.X + b.X, a.Y + b.Y); }
        pdd operator-(pdd a, pdd b) 
        { return pdd(a.X - b.X, a.Y - b.Y); }
        pdd operator*(pdd a, double b)
        { return pdd(a.X*b, a.Y*b); }
        pdd operator/(pdd a, double b)
        { return pdd(a.X/b, a.Y/b); }
        
        double dot(pdd a, pdd b)
        { return a.X*b.X + a.Y*b.Y; }
        double cross(pdd a, pdd b)
        { return a.X*b.Y - a.Y*b.X; }
        double abs2(pdd a) // Square
        { return dot(a, a); }
        double abs(pdd a)
        { return sqrt(dot(a, a)); }

- eps
- 在進行有小數的計算幾何時，常常會有很多的浮點誤差
- eps為誤差容忍值，兩數相差eps內視爲相等