<style> .reveal .slides { text-align: left; font-size:30px; } </style> # 進階計算幾何 ---- - Pick Theorem - Sweep Line - Area of Rectangles - Segment Intersection - Convex Hull trick - Circle cover - Half Plane Intersection --- ## Pick Theorem ### **A = i + b/2 − 1** - A: Area of polygon - i: Grid number in the inner - b: Grid number on the side ---- ### CSES --- Polygon Lattice Points Given a polygon, print two integers: - the number of lattice points **inside the polygon** - the number of lattice points **on its boundary**. - $n\le 10^5$ - $x, y\le 10^6$ --- ### Sweep line - Area of Rectangles - Segment Intersection ---- ## [矩形覆蓋面積](https://cses.fi/problemset/task/1741) ### Area of Rectangles 給定平面上 $n$ 個矩形，求總覆蓋面積。  ---- $n\le 10$ ? <span>$\to$ 排容原理<br><!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$\to$ 求出至少被一個矩形覆蓋的面積 - 至少被兩個 + 至少被三個 ...<br><!-- .element: class="fragment" data-fragment-index="2" --></span> ---- $n\le 10^5$ ? <span>$\to$ 掃描線 !<br><!-- .element: class="fragment" data-fragment-index="1" --></span> ---- 把每個矩形分成 start event 和 end event 掃描線從左往右掃，掃到矩形左界時加入計算面積，掃到右界時移除  ----  ---- 以三個矩形為例，分成六個事件  1. add $(5,5) - (5,15)$ 2. add $(10,10) - (10,20)$ 3. add $(10,20) - (10,25)$ 4. remove $(20,5) - (20,15)$ 5. remove $(20,20) - (20,25)$ 6. remove $(25,10) - (25,20)$ ---- 每次掃描線到新的事件時， 先計算前一個事件與當前事件的掃描區間覆蓋面積  ---- ### add $(5,5) - (5,15)$  ---- ### add $(10,10) - (10,20)$ 到此事件時，加上前一個事件到當前事件的區間覆蓋面積。 area += 10 * (10-5)  ---- ### add $(10,20) - (10,25)$ area += 15 * (10-10)  ---- ### remove $(20,5) - (20,15)$ area += 20 * (20-10)  ---- ### remove $(20,20) - (20,25)$ area += 15 * (20-20)  ---- ### remove $(25,10) - (25,20)$ area += 10 * (25-20)  ---- ### 如何維護區間覆蓋面積 此題的座標範圍為 $\pm 10^6$ 總共 2n 個事件，對於每個事件如何維護當前區間覆蓋面積 ? ---- 離散化 + 資料結構 ! ---- 把所有出現過的 y 座標離散化 最多為長度 2n 的序列  ---- 以 add $(10,10) - (10,20)$ 為例 等價於在時間軸 10 的時候，在區間 1-3(10-20) 加入一個矩形  ---- 線段樹對於每個區間需要維護兩個資訊 - 有多少個矩形覆蓋當前整個區間 - 當前區間覆蓋的總面積為何 ---- 對於每個事件，即可使用資料結構在 $O(\log n)$ 維護 總複雜度為 $O(n\log n)$ --- 給 $n$ $(1\le n\le 2\cdot 10^5)$ 個線段，求是否有任何相交? ---- 之前有教過如何判斷線段相交，窮舉 pair 複雜度為 $O(N^2)$ 但複雜度太高 $(1\le n\le 2\cdot 10^5)$ ---- ## 掃描線 把每條線段分成左右兩端點，從左往右依序加入/移除線段維護 ---- ## 如何維護線段 ? 可以發現如果兩條線段沒有相交， 則他們的上下關係在 在 x 軸重疊的部分不會改變  以線段 A 和 B 為例，A 和 B 在 x 軸重疊的部分，A 始終在 B 的下面 以線段 B 和 C 為例，B 和 C 在 x 軸重疊的部分，B 從下面跑到了上面 ---- 如果線段有相交，則在加入或移除時， 與相鄰的線段相交  在事件 5 中，移除線段 C 時檢查是否與相鄰線段相交。 ---- 因此，每次在加入/移除線段時，判斷是否與當前相鄰的線段相交。 使用平衡二元樹可以在 $O(\log n)$ 快速找到相鄰的線段。 ---- ## 使用平衡二元樹維護 利用上下關係當成偏序關係維護線段，可以使用 set/treap 之類維護 使用 set 維護記得要寫 compare function ---- ### compare function 可以參考以下寫法： 使用線方程式帶入當前掃描線的 $x$ 座標去判斷 $y$ 大小 ```cpp= int nowx; // 掃描線當前 x 座標 double geth(Line p) { long long l = nowx - p.st.x, r = p.ed.x - nowx; return (r * p.st.y + l * p.ed.y) / (double)(l + r); } bool operator<(Line a, Line b) { return geth(a) < geth(b); } set<Line> s; ``` ---- ## 演算法 1. 把所有線段的起始點分成兩個加入/移除 兩個事件 2. 把所有事件照排序 x 軸排序 3. 從左到右掃描事件 - 如果為左端點，把此線段塞入平衡二元樹 - 如果為右端點，把此線段移除平衡二元樹 - 塞入/移除時，判斷是否與前/後一個線段相交 ---- 總複雜度 $O(n\log n)$ --- ### Convex hull trick [link](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/ConvexHulltrick.cpp) - $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/ConvexHulltrick.cpp) - construct function - Conv(convex hull) ---- ## check point inside convex hull given point, return true if point inside convex hull. ```cpp bool contain(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 bool get_tang(Pt p, int &i0, int &i1) ```  ---- ## NCPC 2020 --- M. The Summit from Where I Stand 給一個上半凸包為一座山，$q$ 筆詢問每筆詢問求在位置 $(x, y)$ 時，同時可以看到幾個點  帶入模板找出公切線 index 即可。 ---- ## Find tangent points of a given vector return the index of vertex has max cross value with vector ```cpp int get_tang(Pt vec) ``` ---- ## Find intersection point of a given line - return 1 and intersection is on edge (i, next(i)) - return 0 if no strictly intersection ```cpp bool get_intersection(Pt u, Pt v, int &i0, int &i1) ```  --- ### Circle cover 給定 C 個圓，回傳一個陣列 Area， 其中 Area[i] 為至少包括 i 個圓的覆蓋面積 [link](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/CircleCover.cpp) - init(int _c) - 總共 _c 個圓 - Circ 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 $O(n\log n)$ --- ## NCPC 2021 --- Overlapping Triangles $Q$ 筆詢問，每筆詢問給定兩個三角形，求交集面積 (面積以分數表示) - $Q\le 80$ - $|x|, |y|\le 10^{18}$  ---- 分 case 找交點 ? ---- 轉換為半平面就做完了 XD  --- [HW](https://vjudge.net/contest/575062)