# 【6-5】掃描線演算法

掃描線演算法其實並不是我們第一次遇到，在以前，你比較熟悉的叫法應該是線性掃描，看看下面這題吧！

## 一維最大子陣列問題

**題目**：給定長度為 n 的陣列，求所有連續子矩陣的最大可能總和。（空陣列以 0 計算）

### 解題思路

由於子陣列是連續的，我們進行線性掃描，考慮子陣列是否加入該元素，有以下情況：
* 加入該元素後總和超過最大值 → 加入該元素，更新最大值
* 加入該元素後總和小於最大值，但大於該元素本身 → 加入該元素
* 加入該元素後，總和小於該元素本身 → 捨棄前方子陣列，從該元素開始重新建構

最後就能得到最大值。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int cur = 0;        // 當前最大子陣列和
    int ans = INT_MIN;  // 最大值

    for (int x : a) {
        cur = max(x, cur + x); // 延續或重新開始
        ans = max(ans, cur);   // 更新最大值
    }

    cout << ans << endl;
}

* 時間複雜度：$O(n)$

掃描線演算法也是同理，只不過運用在二維上，通常會有以下步驟：

1. 定義事件
2. 儲存並排序事件
3. 掃描並維護
4. 根據題目需求處理

接下來也會使用這四個步驟來解析幾種常見的題型。

## 最近點對問題

**題目**：給定平面上 $n$ 個點，求曼哈頓距離最近的兩個點。

### 定義事件

平面上有 $n$ 個點，每個點都有座標(x,y)，我們可以簡單定義事件為 x 座標。

### 儲存並排序事件

建立一個陣列儲存點座標，並對所有點按照 x 座標小到大排序。

### 掃描並維護

我們由左而右進行掃描，維護最小距離，而距離的算法根據題目定義，本題是曼哈頓距離。

維護一個活躍集合（有可能產生最小距離的點集合），如果有一個左方的點，其與掃描線的距離已經超過最小距離，則該點不可能與右方的點找到更小的距離了（這句話很重要，多看幾次）。

### 根據題目需求處理

對活躍集合剩下的點，由上而下掃描在最小距離內的點（同理上方對 x 的維護），更新最小距離。

等掃描結束以後，就能得到最小距離。

<details>
<summary>範例程式</summary>

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

int manhattan(pair<int,int> a, pair<int,int> b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> pts(n);
    for (int i = 0; i < n; i++) cin >> pts[i].x >> pts[i].y;

    // 按 x 排序（掃描線從左到右）
    sort(pts.begin(), pts.end());

    set<pair<int,int>> active; // y, x，活躍集合
    int ans = INT_MAX;
    int left = 0;

    for (auto p : pts) {
        // 移除掃描線左側不可能形成更小距離的點
        while (left < n && p.x - pts[left].x > ans) {
            active.erase({pts[left].y, pts[left].x});
            left++;
        }

        // 在活躍集合中檢查 y 座標在最小距離範圍內的點
        auto it_low = active.lower_bound({p.y - ans, -1});
        auto it_high = active.upper_bound({p.y + ans, INT_MAX});
        for (auto it = it_low; it != it_high; ++it) {
            ans = min(ans, manhattan(p, {it->second, it->first}));
        }

        // 將當前點加入活躍集合
        active.insert({p.y, p.x});
    }

    cout << ans << "\n";
}

* 時間複雜度：$O(n\text{ log } n)$

</details>

---

## 2D Maximal Points

**題目**：給定 $n$ 個平面點，找出所有「Maximal Points」：不存在其它點 q 的座標均大於或等於 p 的對應座標，則稱點 p 為 Maximal Points。

### 定義事件

平面上有 $n$ 個點，每個點都有座標(x,y)，我們可以簡單定義事件為 x 座標。

### 儲存並排序事件

建立一個陣列儲存點座標，並對所有點按照 x 座標小到大排序。

### 掃描並維護

從右往左掃描，也就是由 x 大到小掃描每個點，保證了當前點的 x 必定大於或等於其餘左側點。

### 根據題目需求處理

因為 Maximal Points 滿足不存在其它點 q 的座標均大於或等於 p 的對應座標，由掃描已經滿足 x 必定成立，再滿足 y 值大於其餘右側點，就代表該點是 Maximal Point。

* 如果 y > 當前最大 y → 是 Maximal Point → 更新最大 y 值

<details>
<summary>範例程式</summary>

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> pts(n);
    for (int i = 0; i < n; i++) cin >> pts[i].x >> pts[i].y;

    // 按 x 由大到小排序
    sort(pts.begin(), pts.end(), [](const pair<int,int> &a, const pair<int,int> &b){
        return a.x > b.x;
    });

    vector<pair<int,int>> res;
    int maxY = INT_MIN;

    for (auto p : pts) {
        if (p.y > maxY) {
            res.push_back(p);   // 是 maximal point
            maxY = p.y;         // 更新當前最大 y
        }
    }

    cout << res.size() << endl;
    for (auto p : res) cout << p.x << " " << p.y << endl;
}

* 時間複雜度：$O(n\text{ log } n)$

</details>

---

## 矩形重疊問題

題目：給定平面上 $n$ 個矩形的左下角與右上角，每個矩形都有一種顏色，且彼此不相同，又不同矩形組合重疊（不含相鄰）會產生出新顏色，保證不同組合的矩形重疊出來的顏色必定是新的，問平面上的矩形共產生幾種顏色（單獨一個矩形也有顏色，但背景不算一個顏色）。

### 定義事件

平面上有 $n$ 個矩形，每個矩形都有上下左右四條邊，假想一條掃描線由左而右掃過去，會先碰到一個矩形的左邊界，再碰到一個矩形的右邊界，同理由上而下掃描。

既然會有這種特性，我們不妨將邊界定義成一個事件，當掃描線掃過後可能產生以下兩種結果：
1. 碰到的是矩形的左邊界：加入一個新矩形
2. 碰到的是矩形的右邊界：移除一個舊矩形

### 儲存並排序事件

我們將一個矩形的左下角（x1,y1）、右上角（x2,y2）分別存入陣列中，因為我們的事件是 x 座標。並且增加一個變數負責記錄這是左邊界還是右邊界。

這邊舉例使用 1 表示左邊界，-1 表示右邊界，而 index 是我們自定義的矩形編號：

x1 y1 y2 index 1
x2 y1 y2 index -1

之後再利用自定義比較函數根據 x 座標由小排到大就可以進行掃描了。

### 掃瞄並維護

我們由左而右進行掃描，如果還沒離開這個矩形，就又遇到一個新的矩形的左邊界，那這兩個矩形就有可能會重疊。

我們把這些有可能發生重疊的矩形，也就是目前區間活躍的矩形記錄下來，定義一個變數 `prevX` 代表上一個事件的 x 座標，而我們維護的區間就是 `[prevX, x)`。

### 根據題目需求處理

題目要求顏色的總數，也就是有幾種矩形的重疊組合（包含自己），我們可以對於活躍的矩形由上而下再進行一次掃描，套用相同的維護方式，不過這次如果有發生重疊，就直接把活躍的矩形 `index` 存入 `set` 裡面自動去重，最後 `set` 的大小就是答案了。

<details>
<summary>範例程式</summary>

#include <bits/stdc++.h>

using namespace std;

struct Rect {
    int x1, y1, x2, y2;
    // 左下角（x1,y1）、右上角（x2,y2）
};

struct Event {
    int x, y1, y2, id, type; 
    // type = +1 (enter), -1 (exit)
    bool operator<(const Event& other) const {
        return x < other.x; // 依照 x 小到大排序
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; // N 個矩形
    cin >> N;
    vector<Rect> rects(N);
    for (int i = 0; i < N; i++) {
        cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
    }

    // 儲存事件
    vector<Event> events;
    for (int i = 0; i < N; i++) {
        auto [x1,y1,x2,y2] = rects[i];
        events.push_back({x1, y1, y2, i, +1}); // 左邊界 在 x1
        events.push_back({x2, y1, y2, i, -1}); // 右邊界 在 x2
    }
    sort(events.begin(), events.end()); // 排序事件

    set<vector<int>> colorSets; // 存顏色組合
    set<int> activeSet;         // 當前活躍矩形
    int prevX = events[0].x; // 上一個事件，也就是左區間
    int idx = 0;
    
    // 由左而右掃描事件
    while (idx < (int)events.size()) {
        int x = events[idx].x;
        
        // 由上而下掃描活躍區間的矩陣，嘗試更新重疊組合
        if (x > prevX && !activeSet.empty()) {
            for (int y = 0; y < 200; y++) {
                vector<int> cover;
                for (int id : activeSet) {
                    if (rects[id].y1 <= y && y < rects[id].y2) {
                        cover.push_back(id);
                    }
                }
                if (!cover.empty()) {
                    sort(cover.begin(), cover.end()); // 排列方便 set 去重
                    colorSets.insert(cover);
                }
            }
        }

        // 維護活躍區間的矩陣（一次把當前 x 的所有事件處理完再往右走）
        while (idx < (int)events.size() && events[idx].x == x) {
            auto e = events[idx];
            if (e.type == +1) {
                activeSet.insert(e.id); // 加入
            } else {
                activeSet.erase(e.id);  // 移除
            }
            idx++; // 下一個事件
        }
        prevX = x; // 維護左區間
    }

    cout << colorSets.size() << endl;
    return 0;
}

* 時間複雜度：$O(n\text{ log } n)$

</details>

### 練習題
同上題目：[A0077-計算重疊顏色問題](https://code.dali.tc.edu.tw/problem/A0077)

---

聯絡方式：[e-mail]
最後編修時間：2025/09/06 子柚筆