###### tags: `tutorial` # 計算幾何＆其他 by `FHVirus` ---- # 閒聊時間 <iframe width="560" height="315" src="https://www.youtube.com/embed/aLy9rRJ0ApU" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> --- # 大綱 ---- - 暖身題 - 一些基本的運算 - 凸包 - 多邊形面積 - 最遠點對 - 極角排序（Lawfung Sort） - 線段相交 - 座標轉換 - 實作時間／一些不相關的題目 ---- ## 小約定 1. 今天談的東西不是很嚴謹（講者爛）。 2. 沒有特別指名的話都是在討論二維平面上的事。 --- # 暖身 水題大賽？ ---- [CF270A](http://codeforces.com/problemset/problem/270/A) ---- [CF1156A](https://codeforces.com/problemset/problem/1156/A) ---- [CF1096C](https://codeforces.com/problemset/problem/1096/C) ---- [CF195D](https://codeforces.com/problemset/problem/195/D) ---- Naïve! --- # 一些基本的運算 ---- 三角形、多邊形、凸多邊形、直角、面積 大家都會吧？ ---- ## 向量 以下是不嚴謹的簡單的介紹>< ---- ### 想像成箭頭／座標就對了啦ww <iframe width="560" height="315" src="https://www.youtube.com/embed/fNk_zzaMoSs?start=94" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> ---- ### 我們接下來會用到的東西 - 大多是二維向量 - 點積 Dot - 叉積 Cross - 相加相減（Naïve） ---- ### 點積（內積） 大概可以描述兩個向量的方向有多一致。 運算方式：$a \cdot b = a_1 \cdot b_1 + a_2 \cdot b_2 \cdots$ ---- 對於兩個平面的向量： - 若方向相同：$a \cdot b = |a||b|$ - 若兩者垂直：$a \cdot b = 0$ - 若方向相反：$a \cdot b = -|a||b|$ - 一般定義：$a \cdot b = |a||b| \cos \theta$，其中 $\theta$ 為兩向量夾角。 ---- ### [叉積（外積）](https://zh.wikipedia.org/wiki/叉积#/media/File:Cross_product_vector.svg) 常用在計算例舉之類的。 注意到，在二維平面的叉積常常直接取數值， 是因為叉積為三維的向量，且 $a \times b$ 會垂直 $a, b$（垂直平面），運算時多當成數值回傳。 ---- 計算方式： 對於二維的向量而言， $a \times b = a_x \cdot b_y - a_y \cdot b_x$， 注意這會帶正負號。 手算的話也可以以 $a \times b = |a||b| \sin \theta$ 計算。 ---- ### 這可以幹嘛？ 判斷兩個向量的夾角！ --- # 凸包 Convex Hull 別擔心，這裡沒有 DP 優化。 ---- ## 凸包是啥？ > 「凸」的定義是：圖形內任意兩點的連線不會經過圖形外部。 > by [演算法筆記](http://web.ntnu.edu.tw/~algo/ConvexHull.html) 簡單來說，一群點形成的凸包，就是周長最小且包住所有點的殼！ ----  ---- ## 怎麼做？ ---- 掃描、DQ一大堆⋯⋯ 都不是今天要教的！ ---- ## Andrew's Monotone Chain! 上下凸包分開找！ ---- 對於所有點按一軸排序，邊掃邊做事！  ---- ## 要怎麼判斷該不該加點？ 還記得叉積嗎？ ---- ### 拿前兩點判斷！ ---- ### 複雜度 - sort $O(n \log n)$ - 掃描＋Stack 操作 均攤 $O(n)$ 總複雜度 $O(n \log n)$！ ---- ### [例題：TIOJ 1178 Convex Hull](https://tioj.ck.tp.edu.tw/problems/1178) ---- ### 扣的 ```cpp struct point{ ll x, y; point(){} point(ll x, ll y): x(x), y(y){} // 不會用到加法就不做了 point operator-(point p){ return point(x - p.x, y - p.y); } // Dot Product ll operator*(point p){ return x * p.x + y * p.y; } // Cross Product // 注意運算子優先度！ ll operator^(point p){ return x * p.y - y * p.x; } }; ``` ---- ### 扣的 ```cpp // All points, lower convex, upper convex int n; point p[N], lc[N], uc[N]; int lcp, ucp; int32_t main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; FOR(i,n){ int a, b; cin >> a >> b; p[i] = {a, b}; } sort(p, p + n, [](point a, point b){ return a.x < b.x; }); FOR(i,n){ while(ucp > 1 and ((p[i] - uc[ucp - 2]) ^ (uc[ucp - 1] - uc[ucp - 2])) >= 0) --ucp; while(lcp > 1 and ((p[i] - lc[lcp - 2]) ^ (lc[lcp - 1] - lc[lcp - 2])) <= 0) --lcp; uc[ucp++] = p[i]; lc[lcp++] = p[i]; } // 凸包最左最右會重複算到 cout << ucp + lcp - 2 << '\n'; return 0; } ``` ---- 動態凸包什麼的之後再說 ---- ### 習題： - [TIOJ 1371 賢狼之網](https://tioj.ck.tp.edu.tw/problems/1371) --- # 多邊形面積 ---- 大家應該都會算吧？ ---- 應該也不少人看過這個： $$ \begin{align} & \frac{1}{2} \begin{vmatrix} x_1 & x_2 & x_3 & \cdots \\ y_1 & y_2 & y_3 & \cdots \end{vmatrix} \\ = & (x_1 \cdot y_2 - y_1 \cdot x_2) + \cdots + (x_n \cdot y_1 - y_n \cdot x_1) \\ = & v_1 \times v_2 + v_2 \times v_3 + \cdots + v_n \times v_1 \end{align} $$ ---- 這東西對於所有多邊形都可以用！ 按照逆時針排序點， 順時針的話就取個負號， 複雜度 $O(n)$！ ---- ### 就醬，丟題 - [TIOJ 1280 領土 (Territory)](https://tioj.ck.tp.edu.tw/problems/1280) - [TIOJ 1159 房間面積計算](https://tioj.ck.tp.edu.tw/problems/1159) - [Zerojudge d546 剪多邊形](https://zerojudge.tw/ShowProblem?problemid=d546) --- # 最遠點對 ---- 觀察一下不難發現， 最遠點對一定是凸包上的點對！ 怎麼做？ ---- ### $O(n^2)$？ Naïve! ---- ### $O(n)$ ？ ---- ### 建凸包＋雙指針！ 我們沿凸包逆時針進行， 對於遇到的每一個點， 其對應到的最遠點也只會逆時針走！ ----  ---- ### 習題 - [TIOJ 1105 PS3](https://tioj.ck.tp.edu.tw/problems/1105) - 給定 $n$ 個點，求其所形成的最大三角形面積（$n \leq 1500$） --- # 極角排序＆Lawfung Sort ---- [例題：TIOJ 1205 直角三角形](https://tioj.ck.tp.edu.tw/problems/1205) ---- ### $O(n^3)$ ？ Naïve! ---- ### $O(n^2 \log n)$ ？ ---- ### 枚舉每一個點，可以做什麼？ ---- ### 看他是不是直角那個點！ ---- 枚舉每個點當直角， 其他的點按照極角排序好， 雙指針掃過去！ （極角：從 x 軸開始逆時針走的夾角） ---- ### 怎麼照極角排序？ 還記得內外積嗎？ ---- [Lawfung Sort](http://alltherightcodes.blogspot.com/2016/08/tioj-1205.html) ---- ### 小優化 by `warner1129` 把第三、四象限的點以原點對稱過去！ ---- ### 習題 - [AtCoder ABC 139F](https://atcoder.jp/contests/abc139/tasks/abc139_f) --- # 線段相交 應該是本課最難搞的東西 ---- 給你平面上四個點 $A, B, C, D$， 求 $\overline{AB}$ 與 $\overline{CD}$ 有沒有相交？ ---- ### 重點 - 有沒有漏 case ？ - 好好判共線 ---- 想想看？ ----  ---- [例題：TIOJ 1876 回家](https://tioj.ck.tp.edu.tw/problems/1876) ---- 怎麼判斷一個點在不在簡單多邊形內部？ ---- 一個點隨便取一條射線， 若射線交簡單多邊形於奇數個點， 則在多邊形內！ ---- [例題：TIOJ 1423 直線線段相交問題 (Intersection)](w) ---- 怎麼做？ ---- 亂做！ 不要中毒！ --- # 座標轉換 很重要 ---- 例題：[IOI 2007 Pairs](https://tioj.ck.tp.edu.tw/problems/1345) 不要被 IOI 嚇到啦w 這題不難？ ---- ### 一維？ 還算簡單吧？ ---- ### 二維？ - 枚舉每一對 - TLE ---- 從頭想，觀察一下！ 提示：平面距離有分三種。 對於兩個點 $i, j$，他們的距離： - 歐幾里德：$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ - 曼哈頓（計程車幾何）：$|x_i - x_j| + |y_i - y_j|$ - 切比雪夫：$\max(|x_i - x_j|, |y_i - y_j|)$ ---- 可以發現，如果題目要求的是切比雪夫的話，就可以用區間資料結構掃過去！ 但是，要怎麼做？ ----  ---- 展開過程， 如果你上課的時候還看到這邊， 代表 `FHVirus` 沒做完講義， 她會負責現場導一次的。 ---- 這個技巧在二維可以把曼哈頓轉成切比雪夫！ ---- 三維也用一樣的技巧， 只不過你的式子會有四個維度！ ---- ### $\color{green}{AC}$ 恭喜你會一題 IOI 囉！ ---- ### [為什麼很重要？](https://nhspc.csie.ntnu.edu.tw/wp-content/uploads/2020/11/109學年度資訊學科能力競賽決賽試題.pdf) --- # 實作時間／雜題大戰 ---- [ARC113 D](https://atcoder.jp/contests/arc113/tasks/arc113_d) ----