---
tags: Training
---

<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">

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>