<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Geometry ---- - Convex Hull trick - Circle cover - Half Plane Intersection - Polygon Union - Minkowski sum --- ### Convex hull trick - $O(\log n)$ check point inside convex hull - $O(\log n)$ Find 2 tang pts on CH of a given outside point - $O(\log n)$ Find tangent points of a given vector - $O(\log n)$ Find intersection point of a given line ---- [link](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/ConvexHulltrick2.cpp) - construct function - Convex(convex hull) ```cpp #define all(x) x.begin(), x.end() ``` ---- ## check point inside convex hull 給一個點，判斷是否在凸包內、外或者邊上 0: out, 1: on, 2: in ```cpp int inside(Pt p) ``` ---- ## NCPC 2021 --- E. Archery at the Summer Opymlic Camp 給定 $n$ 個凸包，每個凸包一層包一層， $q$ 筆詢問，每筆詢問給一個點，問在幾個凸包內 - $n, q\le 2\cdot 10^5$ ---- 模板可以 $O(\log n)$ 求出是否在某個凸包內，要求出包括幾個凸包可以二分搜。 ---- ## get tangent line of the point Given point $p$, return two point denote the tangent line from point $p$ to convex hull. ```cpp array<int, 2> tangent2(Pt p) ```  ---- The return point is the closest points.  ---- ## NCPC 2020 --- M. The Summit from Where I Stand 給一個上半凸包為一座山，$q$ 筆詢問每筆詢問求在位置 $(x, y)$ 時，同時可以看到幾個點  帶入模板找出公切線 index 即可。 ---- ## Find tangent points of a given vector return the idx of far/closer tangent point v (min cross value) ```cpp int tangent(Pt v, bool close = true) ```  ---- ## Find intersection point of a given line - return 2 index if intersection on the 2 points - return 1 index if intersection on the 1 point - return 0 index if no intersection intersection is on edge (i, next(i)) ```cpp vector<int> intersect(Line L) ```  --- ### Circle cover 給定 C 個圓，回傳一個陣列 Area， 其中 Area[i] 為至少包括 i 個圓的覆蓋面積 [link](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/CircleCover.cpp) - init(int _c) - 總共 _c 個圓 - Circle c[ N ] - 填入圓的圓心&半徑 - solve() - 跑 CircleCover $O(n^2\log n)$ --- ### 半平面交 ### Half Plane Intersection ---- ### 半平面 每條直線能把平面切成兩半。 以方程式 $ax+by+c\le0$ 可以代表一個半平面。  $5x + 3y \le 5$ ---- ### 半平面交 半平面交為多個半平面的交集區域，通常為一個凸多邊形  - $5x + 3y - 5\le 0$ - $2 x-3 y + 7\le 0$ ---- 以下三個半平面圍成一個凸多邊形  - $5x + 3y - 5\le 0$ - $2 x-3 y + 7\le 0$ - $-2 x+0 y - 15\le 0$ ---- ## 模板 [[line define]](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/definition.cpp) [[link]](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/Half_plane_intersection.cpp) ```cpp vector<Pt> HPI(vector<Line>& L) ``` 傳入每條方程式的兩點方程式 (半平面為點 $st$ 往 $ed$ 的逆時針方向) 回傳值為形成的凸多邊形的頂點 vector (須保證結果為凸包) 半平面交沒有交集會回傳空的 vector $O(n\log n)$ ---- ## NCPC 2021 --- Overlapping Triangles $Q$ 筆詢問，每筆詢問給定兩個三角形，求交集面積 - $Q\le 80$ - $|x|, |y|\le 2^{32}$  ---- 題目等價於給定兩個凸多邊形，求兩個凸多邊形的交集 ---- 轉換為半平面就做完了 XD  --- ## Polygon Union 求 n 個多邊形的聯集面積 複雜度 O(n^2\log n) ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/polyUnion.cpp) ```cpp double polyUnion(vector<vector<Pt>> py) ``` 傳入多個多邊形，每個多邊形為一個 vector\<Pt\> 回傳值為多邊形的聯集面積 ---- ## Polygon Cover Area[i] : area covered by at least i polygon $O(n^2\log n)$ [code](https://github.com/warner1129/CompetitiveProgrammingCodebook/blob/master/code/Geometry/UnionOfPolygons.cpp) --- ## Minkowski sum 對於給定的兩個點集合 $A$ 和 $B$。 Minkowski sum 為 $\{a + b\ |\ a\in A, b\in B\}$。  ---- 將 Minkowski sum 視覺化，為一個凸包 A 繞著凸包 B 轉一圈。 並且兩個凸包 A 和 B 上的邊會在 Minkowski sum 中出現。  ---- 幾個性質 - 兩個凸多邊形的 Minkowski sum，也會是凸多邊形 - P 和 Q 組成的 Minkowski sum 最多有 |P|+|Q| 個點。 - 在凸包 A 和 B 上的邊也會在 Minkowski sum 上出現。 ---- 模板 (Minkowski sum of convex polygons) 複雜度 $O(N)$ [link](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/Minkowski_Sum.cpp) ```cpp vector<Pt> minkowski(vector<Pt> P, vector<Pt> Q) ``` 把多邊形 p 和 q 丟進去 minkowski，回傳的 vector 為組成的凸多邊形。 丟進去的多邊形要保證為照逆時針順序給，出來的也是逆時針順序的。 ---- ## Minimum Distance of two Convex Polygon 給兩個凸多邊形 $A$ 和 $B$，求出凸兩個多邊形的最近距離。 ---- 等價於從 $A$ 中找出一個點 $a$，$B$ 中找出一個點 $b$， 使得 $|a-b|$ 最小，也就是最靠近 (0, 0) 的點。 ---- 如果我們將 $B$ 的點都取負和 $A$ 去做 Minkowski sum。 也就是 Minkowski sum = $A$ + $(-B)$ ---- 求出來的集合為 $\{a - b\ |\ a\in A, b\in B\}$。 從中取出 $| a-b |$ 最小的值，即為兩個多邊形的最近距離。 --- ## Intersection of polygon and circle [圓 definition](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/definition.cpp) [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/Intersection_of_polygon_and_circle2.cpp) ```cpp= ld PCIntersect(vector<Pt> v, Circle cir) ``` 傳入多邊形和圓，回傳交集面積 ---- ## Intersection of two circles 找出兩圓的交點 [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/Intersection_of_two_circles.cpp) 回傳 vector 為交點，若為空代表沒有交點。 ---- ## Tangent line of two circles 求出兩圓的切線 [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/Tangent_line_of_two_circles.cpp) sign1 傳入 1 求外公切線 sign1 傳入 -1 求內公切線 回傳值為 vector\<Line\>，對於每條切線 Line 第一個點為第一個圓切點位置 Line 第二個點為第二個圓切點位置 --- 今天教的幾何內容不多 但實際上需要花的整理時間是所有主題中最多的 建議每個模板都測過再放到各自的 codebook 如果沒測過不建議比賽中直接試(~~通常會直接試到比賽結束~~) ---- 幾何的內容如果現場推會需要不少時間 算是一個能先準備先賺到的主題 (軍備競賽) 可以多看別人的 codebook 去多放一些經典問題模板 但要記得修改成自己的幾何 definition 能用的樣子 但都要自己測過題目，需要額外一些經典題目可以跟 jakao 要 ---- 三角函數求切線等等幾何問題 如果遇到浮點數問題 記得在內建函數後面加 l $sin(x)\to sinl(x)$ $sqrt(x)\to sqrtl(x)$ $atan2(x)\to atan2l(x)$ 以避免不必要的 debug