# 110 選手班 - 計算幾何 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.25 --- ## Outline - 2D-Vector - Segments - Sort by Angle - Convex Hull - Duality of Points and Lines --- ## 2D-Vector ---- ### 向量運算 - 加法 - 減法 - 乘法 - 除法 ---- ```c= using GT = long long ; struct Pt { GT x, y ; Pt operator+(const Pt b) const { return Pt{x+b.x, y+b.y} ; } Pt operator-(const Pt b) const { return Pt{x-b.x, y-b.y} ; } Pt operator*(const GT b) const { return Pt{x*b, y*b} ; } Pt operator/(const GT b) const { return Pt{x/b, y/b} ; } bool operator==(const Pt b) const { return x == b.x && y == b.y ; } double len () { return sqrt(x*x + y*y) ; } GT norm () { return x*x + y*y ; } }; ``` ---- ### Dot - 內積 - $(x_1, y_1) \cdot (x_2, y_2)=x_1x_2 + y_1y_2$ - 兩個向量在同一方向的程度 ---- ### Cross - 外積 - $(x_1, y_1) \times (x_2, y_2)=x_1y_2 - x_2y_1$ - 兩個向量的垂直程度，逆時鐘為正 ---- ```c= GT dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y ; } GT cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x ; } ``` ---- ### Orientation - 兩個向量的方向性 - 逆時針：1 - 順時針：-1 - 平行：0 - cross ---- ```c= int ori(Pt a, Pt b) { GT ret = cross(a, b) ; if(ret == 0) return 0 ; return ret < 0 ? -1 : 1 ; } ``` ---- ### Area - 兩個夾角形成有向面積 - 逆時針：正數 - 順時針：負數 - $\vec{A} 與 \vec{B}$ 的夾角面積：$\vec{A} \times \vec{B}$ ---- 多邊形面積 - 切成到原點的多個三角形 - 依照點的順序計算有向面積加總 ----  --- ## Segments ---- ### In Segment - 給定一個點及線段 - 請判斷點是否在線段內 ---- - 線段 $(A,B)$，點 $P$ - 直線上：$\text{cross}(\overrightarrow{AB}, \overrightarrow{AP}) = 0$ - 線段內：$\text{dot}(\overrightarrow{PA}, \overrightarrow{PB}) \leq 0$ ---- ```c= bool in_segment(Pt a, Pt b, Pt p){ return ori(b-a, p-a) == 0 && dot(p-a, p-b) <= 0 ; } ``` ---- ### Segment Intersection - 給定兩個線段 - 請判斷兩個線段是否相交 ---- - 線段 $(A,B)$，$(C,D)$ - 只有一個點在線段內：in_segment - 嚴格相交：將彼此切割成兩半 - $\text{ori}(\overrightarrow{AB}, \overrightarrow{AC}) \times \text{ori}(\overrightarrow{AB}, \overrightarrow{AD}) < 0$ - $\text{ori}(\overrightarrow{CD}, \overrightarrow{CA}) \times \text{ori}(\overrightarrow{CD}, \overrightarrow{CB}) < 0$ ---- ```c= bool banana(Pt a, Pt b, Pt c, Pt d) { if( in_segment(a, b, c) || in_segment(a, b, d) || in_segment(c, d, a) || in_segment(c, d, b)) return true ; return ori(b-a, c-a) * ori(b-a, d-a) < 0 && ori(d-c, a-c) * ori(d-c, b-c) < 0 ; } ``` --- ## Sort by Angle ---- ### Trigonometric Functions - $\cos(\theta)$ \ $\sin(\theta)$ \ $\tan(\theta)$ - $\theta$ 參數為弧度制 - Time > $\mathcal{O}(1)$ - 用泰勒展開式等實作 ---- ### atan2 - Returns the principal value of the arc tangent of y/x, expressed in radians. --cplusplus.com - 回傳值域：$(-\pi, \pi]$  ---- ### Solution 1 - sort by atan2 ```c= bool cmp(Pt a, Pt b) { return atan2(a.x, a,y) < atan2(b.x, b.y) ; } ``` ---- - 優點：直觀、簡單 - 缺點：慢、浮點數誤差 ---- ### Solution 2 - sort by cross ```c= bool cmp(Pt a, Pt b) { bool f1 = a.x < 0 || (a.x == 0 && a.y < 0) ; bool f2 = b.x < 0 || (b.x == 0 && b.y < 0) ; if(f1 != f2) return f1 < f2 ; return cross(a, b) > 0 ; } ``` ---- - 切成兩半，各自外積判斷 - 優點：快速、正確 - 缺點：麻煩 --- ## Convex Hull ---- ### Convex - 凸多邊形 - 圖形內任兩點連線皆在圖形內部 - 所有內角小於 $180$ 度 ----  ---- ### Convex Hull - 包含所有點的最小凸多邊形  ---- ### Andrew's Monotone Chain - 將所有點依照 $(x,y)$ 排序 - 把下凸包圍出來 - 把上凸包圍出來 - 合併上下凸包 ----  ---- ### 圍下凸包 - 兩條邊的內角小於 $180$ 度 - 點 $A, B, C$ 依照 $(x,y)$ 排序 - 若 $\text{cross}(\overrightarrow{AB}, \overrightarrow{BC}) \leq 0$ 則 $B$ 不在凸包上 ---- - 以 stack 維護目前凸包 - 對於新加入的點，檢查前一個點是否在凸包上 - 下凸包：$0 \rightarrow N$ 逆時針旋轉 - 上凸包：$N \rightarrow 0$ 逆時針旋轉 ---- https://upload.wikimedia.org/wikipedia/commons/9/9a/Animation_depicting_the_Monotone_algorithm.gif ---- ### Time Complexity - Sort：$\mathcal{O}(N\log N)$ - Construct：$\mathcal{O}(N)$ - Total：$\mathcal{O}(N\log N)$ ---- ```c= vector<Pt> convex(vector<Pt> v){ vector<Pt> ret ; sort(v.begin(), v.end()) ; int k = 0 ; for(auto i:v){ while(k >= 2 && ori(ret[k-1] - ret[k-2], i - ret[k-1]) <= 0) ret.pop_back(); ret.push_back(i) ; ++k ; } v.pop_back(); int hf = --k ; reverse(v.begin(), v.end()); for(auto i:v){ while(k - hf >= 2 && ori(ret[k-1] - ret[k-2], i - ret[k-1]) <= 0) ret.pop_back(); ret.push_back(i) ; ++k ; } return ret; } ``` ---- ### Application - 最大值問題 - 最遠點對 - 最小包覆矩形 - 旋轉卡尺 - 邊斜率單調 - 最大三角形 ---- http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html ---- ### 整數點限制 - 座標範圍 $[0,C]$ - 凸包上至多 $\mathcal{O}(\sqrt C)$ 個點 - 直接暴力枚舉最遠點對 ---- ### 直線與凸包 - 把一堆直線丟進平面 - 若只關心最上方的函數，將會形成一個下凸包 ----  ---- ### Envelope - 快速尋找某個 $x$ 在多個線性函數下的最大值 - Find $\max(f_i(x)=a_ix+b_i)$ - 凸包上的函數斜率具有單調性 - 對函數三分搜 $\mathcal{O}(\log N)$ - DP 斜率優化 --- ## Duality of Points and Lines ---- ### Problem - 給定 $N$ 個點 - 請支援以下詢問 $Q$ 次 - 給定一條直線 $f(x) = ax + b$，請問是否所有點皆在直線上方？ - $N, Q \leq 10^6$ ---- - $\forall i,\ y_i \geq f(x_i) = ax_i + b$ - $-b \geq ax_i - y_i$ - $(-b) \geq x_i (a) - y_i$ - 點 $(a, -b)$ 在直線 $f(t) = x_i(t) - y_i$ 上方 ---- - 所有點 $(x_i, y_i)$ 在直線 $f(x) = ax+b$ 上方 - $\Rightarrow$ 點 $(a, -b)$ 在所有直線 $f_i(t) = x_i(t) - y_i$ 上方 - $\Rightarrow$ 點 $(a, -b)$ 在所有直線 $f_i(t)$ 所構造出的下凸包之上 ---- - 排序所有直線 $f_i(t)$：$\mathcal{O}(N\log N)$ - 每次詢問檢查點是否在凸包上方：$\mathcal{O}(\log N)$ - Total：$\mathcal{O}(N\log N + Q\log N)$ ---- ### Key - 對偶性質：點 $\Longleftrightarrow$ 直線 - 多個點與一條線 $\Longleftrightarrow$ 多條線與一個點 - 改變題目的性值以幫助解題 ---- ### 類題 - CF 678F --- ## Credit - 資訊之芽 - 演算法筆記 - Wikipedia - OI Wiki - IONC - https://ithelp.ithome.com.tw/m/articles/10210364 - https://codeforces.com/blog/entry/63823