<style> .reveal .slides { text-align: left; } </style> # stack Competitive programming 2 2021/12/13 ---- * 最大子矩陣 * 凸包 --- ## 最大子矩陣 <div style="font-size: 30px"> 題目給你 $N \times M ( N, M \le 2000)$ 的矩陣，上面有一些格子有障礙物， 要找出一個子矩陣，沒有任何障礙物。 問你所有合法的子矩陣中，最大面積為多少?  以上圖為例，假設黑色為障礙物，則合法中最大的子矩陣為紅色框起來的，面積為6 </div> ---- ## 想法1 <div style="font-size: 30px"> 暴力窮舉所有矩陣判斷合不合法 $O(N^6)$ * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ * 窮舉矩陣內的每一格判斷是否有障礙物 $O(N^2)$ </div> ---- ## 想法2 <div style="font-size: 30px"> * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ * ~~窮舉矩陣內的每一格判斷是否有障礙物 $O(N^2)$~~ 計算前綴和，左上到每個點為右下的矩形裡面的障礙物數量  如果要計算區間內的障礙物數量，用排容原理 假設要求 [2,2] 到 [3,4] 子矩陣的障礙物數量 則為 prefix[3][4] - prefix[3][1] - prefix[1][4] + prefix[1][1] </div> ---- * 窮舉左上角 $O(N^2)$ * 窮舉右下角 $O(N^2)$ 複雜度 $O(N^4)$ ---- ## 想法3 <div style="font-size: 30px"> ### DP 先 $O(N^2)$ 計算出每格往上最高可以到多高  之後窮舉以每格為右下角的所有可能矩形 每次往左判斷從起始格到當前往上最高可以多高 以 [3,4] 為例 往左 1 格高度最高可以為 2 往左 2 格高度最高可以為 2 往左 3 格高度最高可以為 1 </div> ---- * 窮舉右下角 $O(N^2)$ * 窮舉左界 $O(N)$ 複雜度 $O(N^3)$ 但...還不夠 $N^3 = 8 \cdot 10^9 \to TLE$ ---- ## 正解 <div style="font-size: 30px"> 先 DP 每個點往上最多可以幾格 我們需要用到 stack 來做 一樣窮舉以每個點當右下，然後順便更新答案 </div> ---- <div style="font-size: 30px"> 其實對於每一列都可以轉換成一下問題  做法如下 每次遇到一個更高的高度把它放進stack 而遇到較低的就更新答案 $O(N^2)$ </div> --- ## 凸包 <div style="font-size:25px"> 你有n個點，然後你要找出一個凸多邊形可以圍住這n個點且面積最小， 這個凸多邊形稱為凸包 你也可以想成凸包是用一條橡皮筋把牆壁上的圖釘圈起來的範圍 </div>  ----  ---- ## Andrew's Monotone Chain (競賽常用的做法) ---- <div style="font-size:30px"> 作法為分別求出上下凸包，求完之後再和再一起， 上半凸包+下半凸包=完整的凸包 </div>  ---- 先求下凸包 <div style="font-size:30px"> 1. 先將全部點照$x$大小排序,再排$y$大小 2. 依序嘗試將點加入凸包判斷是否合法 3. 不合法刪掉前面最後一個點，合法則將點加進凸包 </div> ---- 如何判斷合法 <div style="font-size:30px; text-align:left"> 首先先觀察凸包，若我們從左到右依序看點，會發現下一個向量都是在前一個向量的逆時鐘方向 像是 $\overrightarrow{P_2 P_3}$ 會在 $\overrightarrow{P_2 P_4}$ 的逆時鐘方向 </div>  ----  <div style="font-size:25px; text-align:left"> 而 $\overrightarrow{P_{i} P_{i+1}}$ 若是在$\overrightarrow{P_{i} P_{i+2}}$ 的逆時鐘方向，則$\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} > 0$ 因此如果 $\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} \le 0$ 代表前一個點會在凸包裡面， 而不會在凸包上，就可以把前一個點刪掉，再把新的點加進去凸包裡面 </div> ---- <div style="font-size:30px; text-align:left"> 而實作可以用一個stack去維護， 一開始先把前兩個點直接加進去stack之後每一個點$P_i$都去判斷， 向量是不是往逆時針方向 ( $\overrightarrow{P_{i-2} P_{i-1}} \times \overrightarrow{P_{i-2} P_{i}} > 0$ ) 若非法則把stack的top刪掉，一直刪到合法為止， 再把新的點加進去凸包 </div> ---- <div style="margin-left:-100px"> ```cpp= struct Pt{ int x,y; Pt(){} Pt(int _x,int _y){ x=_x,y=_y; } friend bool operator<(const Pt& lhs,const Pt& rhs){ return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x; } friend Pt operator-(const Pt& lhs,const Pt& rhs){ return Pt(rhs.x-lhs.x,rhs.y-lhs.y); } friend int cross(const Pt& o,const Pt& a,const Pt& b){ Pt lhs = o-a, rhs = o-b; return lhs.x*rhs.y - lhs.y*rhs.x; } }; vector<Pt> convex_hull(vector<Pt> hull){ sort(hull.begin(),hull.end()); int top=0; vector<Pt> stk; for(int i=0;i<hull.size();i++){ while(top>=2&&cross(stk[top-2],stk[top-1],hull[i])<=0) stk.pop_back(),top--; stk.push_back(hull[i]); top++; } for(int i=hull.size()-2,t=top+1;i>=0;i--){ while(top>=t&&cross(stk[top-2],stk[top-1],hull[i])<=0) stk.pop_back(),top--; stk.push_back(hull[i]); top++; } stk.pop_back(); return stk; } ``` 排序 $O(NlgN)$ + 找凸包 $O(N)$ 複雜度 $O(NlgN)$ </div> --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/473029) <div style="font-size: 30px"> 提交期限到下星期一 12/20 23:59 截止 </div>