stack

暴力窮舉所有矩陣判斷合不合法 \(O(N^6)\)

• 窮舉左上角 \(O(N^2)\)
• 窮舉右下角 \(O(N^2)\)
• 窮舉矩陣內的每一格判斷是否有障礙物 \(O(N^2)\)

• 窮舉左上角 \(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]

DP

先 \(O(N^2)\) 計算出每格往上最高可以到多高

之後窮舉以每格為右下角的所有可能矩形

每次往左判斷從起始格到當前往上最高可以多高

以 [3,4] 為例
往左 1 格高度最高可以為 2
往左 2 格高度最高可以為 2
往左 3 格高度最高可以為 1

先 DP 每個點往上最多可以幾格

我們需要用到 stack 來做

一樣窮舉以每個點當右下，然後順便更新答案

其實對於每一列都可以轉換成一下問題

做法如下
每次遇到一個更高的高度把它放進stack

而遇到較低的就更新答案

\(O(N^2)\)

作法為分別求出上下凸包，求完之後再和再一起，
上半凸包+下半凸包=完整的凸包

1. 先將全部點照\(x\)大小排序,再排\(y\)大小
2. 依序嘗試將點加入凸包判斷是否合法
3. 不合法刪掉前面最後一個點，合法則將點加進凸包

首先先觀察凸包，若我們從左到右依序看點，會發現下一個向量都是在前一個向量的逆時鐘方向
像是 \(\overrightarrow{P_2 P_3}\) 會在 \(\overrightarrow{P_2 P_4}\) 的逆時鐘方向

而 \(\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\) 代表前一個點會在凸包裡面，
而不會在凸包上，就可以把前一個點刪掉，再把新的點加進去凸包裡面

而實作可以用一個stack去維護，
一開始先把前兩個點直接加進去stack之後每一個點\(P_i\)都去判斷，
向量是不是往逆時針方向 ( \(\overrightarrow{P_{i-2} P_{i-1}} \times \overrightarrow{P_{i-2} P_{i}} > 0\) )
若非法則把stack的top刪掉，一直刪到合法為止，
再把新的點加進去凸包

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)\)