9.1K 688 109

Đã đăng vào thg 5 3, 8:00 SA 13 phút đọc

228

Thuật toán Đường quét (Sweep line algorithm)

I. Giới thiệu

Trong hình học tính toán, việc xét các điểm trên một mặt phẳng là bài toán thường xuyên xảy ra. Tuy nhiên, với dữ liệu lớn trong các bài toán Lập trình thi đấu, việc quét qua tất cả mọi điểm trên mặt phẳng dường như là bất khả thi, chính vì thế ta sẽ chỉ xét tới một số điểm cần thiết mà thôi.

Thuật toán đường quét (Sweep line algorithm) được xây dựng dựa trên tư tưởng nói trên. Đây là một thuật toán mạnh trong hình học tính toán, ý tưởng của nó rất đơn giản: Sử dụng một đường thẳng dọc và "quét" qua mặt phẳng.

Trước khi đọc bài viết này, độc giả cần nắm vững các kiến thức sau:

Lý thuyết khoảng cách: Với hai điểm $P(x_P, y_P)$ $P (x_{P}, y_{P})$ và $Q(x_Q, y_Q)$ $Q (x_{Q}, y_{Q})$ trên mặt phẳng $Oxy,$ $O x y,$ ta có hai khái niệm:
- Khoảng cách Euclid giữa hai điểm $P$ và $Q$ là khoảng cách thu được khi tính bằng công thức Pythagoras:
  $\sqrt{(x_P - x_Q)^2 + (y_P - y_Q)^2}$
- Khoảng cách Mahattan giữa hai điểm $P$ và $Q$ là khoảng cách thu được nếu như ta chỉ được đi dọc hoặc ngang từ điểm này qua điểm kia:
  $|x_Q - x_P| + |y_Q - y_P|$
Các kĩ thuật bổ trợ: Kĩ thuật Hai con trỏ, Kĩ thuật Rời rạc hóa (Nén số).
Các cấu trúc dữ liệu bổ trợ: Cây phân đoạn, Cây chỉ số nhị phân.
Thuật toán Bao lồi.

Những kiến thức nói trên sẽ được sử dụng để lọc ra và xử lý các điểm cần quan tâm trong quá trình quét trên mặt phẳng. Vì thế, các bạn hãy đọc kĩ tất cả các bài viết về các chủ đề trên trước khi nghiên cứu bài viết này.

Bây giờ, chúng ta sẽ cùng phân tích ý tưởng của Thuật toán đường quét thông qua những bài toán kinh điển trên mặt phẳng!

II. Các bài toán minh họa

1. Bài toán tìm cặp điểm gần nhất

Đề bài

Cho $n$ điểm trên mặt phẳng tọa độ $Oxy$ . Khoảng cách giữa hai điểm trên mặt phẳng này được định nghĩa là khoảng cách Euclid.

Yêu cầu: Tìm cặp điểm có khoảng cách Euclid gần nhau nhất?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ - số lượng điểm.
Trên $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ - tọa độ điểm thứ $i$ .

Ràng buộc:

$1 \le n \le 50000$ .
$|x_i|, |y_i| \le 10^6; \forall i: 1 \le i \le n$ .

Output:

Đưa ra chỉ số $a$ và $b$ của cặp điểm gần nhau nhất và khoảng cách giữa chúng, làm tròn tới $6$ chữ số sau dấu chấm thập phân.

Sample Input:

Sample Output:

1 2 1.000000

Ý tưởng

Chắc chắn ý tưởng xét mọi cặp điểm sẽ gây ra TLE. Tuy nhiên, thuật toán đường quét sẽ giúp giảm độ phức tạp xuống chỉ còn $O(n \times \log n)$ .

Đầu tiên ta sắp xếp lại các điểm theo thứ tự hoành độ tăng dần. Lần lượt duyệt qua từng điểm trong danh sách đã sắp xếp (tưởng tượng như có một đường thẳng dọc đang "quét" qua các điểm), sau đó ta sẽ tìm ra một số điểm "đáng quan tâm" để xét khoảng cách với điểm đang duyệt, sao cho chi phí xét các điểm đáng quan tâm này không vượt quá $O(\log n)$ . Nhờ thế, thuật toán sẽ được cải tiến độ phức tạp về $O(n \times \log n)$ .

Giả sử ta đã xử lý xong $i - 1$ điểm, và khoảng cách ngắn nhất hiện có là $d$ . Như vậy từ điểm thứ $i$ trở đi, ta sẽ chỉ cần xem xét các điểm có khoảng cách tới nó nhỏ hơn $d$ . Gọi điểm đang xét là $i = p(x_i, y_i)$ . Ta có bổ đề dưới đây:

Bổ đề 1:

Tại mỗi bước trong thuật toán, để tìm ra một cặp điểm có khoảng cách bé hơn $d,$ ta chỉ cần quan tâm tới tối đa $8$ điểm khác.

Chứng minh:

Từ điểm $i = p(x_i, y_i),$ ta vẽ $8$ hình vuông xung quanh, mỗi hình vuông có cạnh đúng bằng $\frac{d}{2}$ (điểm màu xanh là điểm $p_i$ ):

Dễ thấy các điểm từ $1$ tới $i - 1$ đều nằm về bên trái của điểm đang xét, do ta đã sắp xếp các điểm tăng dần theo hoành độ. Nhận xét rằng, từ $p_i$ ta không cần quan tâm tới các điềm nằm ngoài $8$ hình vuông trên, do khi đó khoảng cách giữa chúng sẽ lớn hơn $d$ .

Với $8$ hình vuông vừa vẽ, do $d$ là khoảng cách ngắn nhất giữa hai điểm bất kì trong $i - 1$ điểm đầu tiên, nên trong mỗi hình vuông, ta chỉ có tối đa $1$ điểm có thể ghép với $p_i$ để tạo ra một cặp điểm có khoảng cách tốt hơn. Do đó, ta chỉ cần xét tối đa $8$ điểm trong $8$ hình vuông để cập nhật kết quả.

Từ bổ đề $1,$ ta nhận thấy cần duy trì một danh sách $L$ các điểm có hoành độ chênh lệch không quá $d$ so với điểm đang xét. Do $d$ giảm dần qua các bước của thuật toán, nên việc này có thể thực hiện bằng kĩ thuật hai con trỏ. Đồng thời, tại mỗi bước ta cần tìm các điểm có tung độ lân cận với điểm đang xét. Do đó các điểm trong $L$ cần được sắp xếp theo thứ tự tung độ tăng dần. Cấu trúc dữ liệu phù hợp ở đây sẽ là std::set.

Thuật toán cụ thể sẽ trải qua các bước như sau:

Sắp xếp danh sách các điểm theo hoành độ tăng dần.
Lần lượt duyệt qua các điểm trong danh sách, đồng thời duy trì một std::set $s$ .
Gọi $d$ $d$ là khoảng cách nhỏ nhất đã có, tại mỗi bước xét điểm $p_i$ $p_{i}$ ta thực hiện:
- Loại bỏ khỏi $s$ các điểm có chênh lệch hoành độ so với điểm đang xét lớn hơn $d$ .
- Tìm các điểm trong $s$ có chênh lệch tung độ không quá $d,$ tính khoảng cách giữa các điểm này với $p_i$ và cập nhật $d$ .
- Thêm điểm $p_i$ đang xét vào $s$ .

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Point
{
    int x, y;
    int id;

    bool operator < (const Point& other)
    {
        if (x != other.x)
            return x < other.x;

        return y < other.y;
    }
};

struct cmp
{
    bool operator()(const Point& a, const Point& b)
    {
        if (a.y != b.y)
            return a.y < b.y;

        return a.x < b.x;
    }
};

int sqr_distance(Point a, Point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

void solution(int n, vector < Point >& p)
{
    sort(p.begin() + 1, p.end());

    // Ban đầu giả sử kết quả tốt nhất là khoảng cách giữa hai điểm đầu tiên.
    int sqr_d = sqr_distance(p[1], p[2]);
    int id1 = 1, id2 = 2;

    set < Point, cmp > s;
    for (int i = 1; i <= n; ++i)
    {
        int x = p[i].x, y = p[i].y, id = p[i].id;
        int d = sqrt(sqr_d);
        Point cur = {-1000001, y - d, id};

        while (true)
        {
            // Sử dụng hàm upper_bound của set, tìm ra điểm có hoành độ nhỏ nhất
            // thỏa mãn tung độ >= (y - d).
            auto it = s.upper_bound(cur) ;
            if (it == s.end())
                break;

            // Nếu điểm đầu tiên có tung độ >= (y - d) mà lại
            // lớn hơn hẳn cả y + d thì dừng luôn.
            cur = *it;
            if (cur.y > y + d)
                break;

            // Xóa điểm này nếu như nó có hoành độ bé hơn x - d.
            // Trong set dần dần sẽ chỉ còn lại các điểm có hoành độ >= x - d
            // và tung độ nằm trong đoạn [y - d, y + d].
            if (cur.x < x - d)
            {
                s.erase(it);
                continue;
            }

            if (sqr_distance(p[i], cur) < sqr_d)
            {
                sqr_d = sqr_distance(p[i], cur);
                id1 = id;
                id2 = cur.id;
            }
        }

        s.insert(p[i]);
    }

    if (id1 > id2)
        swap(id1, id2);
    cout << id1 << ' ' << id2 << ' ';
    cout << fixed << setprecision(6) << sqrt(sqr_d);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector < Point > p(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }

    solution(n, p);

    return 0;
}

Đánh giá

Ta nhận thấy, mỗi điểm được thêm vào và xóa khỏi set không quá $1$ lần, do đó tổng chi phí cho các thao tác thêm và xóa điểm là $O(n \times \log n)$ .

Chi phí sắp xếp các điểm ban đầu là $O(n \times \log n)$ .

Tại mỗi bước, chi phí tìm kiếm là $O(\log n)$ và có tối đa $8$ điểm cần xét.

Như vậy, độ phức tạp tổng quát là:

Độ phức tạp thời gian: $O(n \times \log n)$ .
Độ phức tạp không gian: $O(n)$ .

2. Bài toán tìm tổng diện tích phủ bởi các hình chữ nhật

Đề bài

Trên mặt phẳng tọa độ $Oxy,$ vẽ $n$ hình chữ nhật có cạnh song song với các trục tọa độ.

Yêu cầu: Tính tổng diện tích trên mặt phẳng bị che phủ bởi $n$ hình chữ nhật này?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ .
Trên $n$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_1, y_1, x_2, y_2$ biểu thị tọa độ góc trái dưới và góc phải trên của một hình chữ nhật.

Ràng buộc:

$1 \le n \le 10^4$ .
$0 \le x_1 \le x_2 \le 3 \times 10^4; 0 \le y_1 \le y_2 \le 3 \times 10^4$ .

Output:

In ra diện tích bị phủ bởi $n$ hình chữ nhật.

Sample Input:

2
10 10 20 20
15 15 25 30

Sample Output:

Ý tưởng

Tư tưởng chung của thuật toán đường quét là sử dụng một đường thẳng dọc quét qua mặt phẳng, và bài toán này cũng không ngoại lệ.

Thay vì xử lý từng hình chữ nhật, thì ta sẽ tách mỗi hình chữ nhật thành hai "sự kiện": Một sự kiện biểu thị cạnh bên trái, một sự kiện biểu thị cạnh bên phải của hình chữ nhật. Lúc này, thực chất ta đang lưu lại các đoạn thẳng theo chiều dọc với trạng thái là $(x, y_1, y_2)$ - Đoạn thẳng có hoành độ $x,$ kéo dài từ tung độ $y_1$ tới $y_2$ .

Đồng thời, ta duy trì một tập $s$ chứa các hình chữ nhật mà đường quét đang cắt qua.

Ta biết được những hình chữ nhật nào đang bị cắt bởi đường quét của chúng ta (màu đỏ). Để tìm tổng diện tích được bao phủ, ta sẽ tìm diện tích từng phần bị bao phủ giữa mỗi cặp hai đoạn thẳng liền nhau và tính tổng của chúng (trước đó các đoạn thẳng đã được lưu lại và sắp xếp tăng dần theo hoành độ). Để tìm phần diện tích được bao phủ giữa hai đoạn thẳng liền nhau, ta cần biết tổng độ dài phần đường quét đi qua chúng (nét liền màu xanh trong hình trên). Nhân độ dài này với khoảng cách giữa hai đoạn thẳng liền nhau, ta được diện tích của phần hình chữ nhật giữa hai "sự kiện" đó.

Vấn đề đặt ra là làm thế nào để tìm tổng độ dài của các phần "nét liền màu xanh" như trên hình. Hãy nhớ rằng tại mỗi bước ta duy trì một tập $s$ các hình chữ nhật mà đường thẳng quét cắt qua. Hiển nhiên ta thấy tổng độ dài của phần "nét liền màu xanh" chính là hợp của tất cả các hình chữ nhật trong tập $s$ tại mỗi bước.

Thuật toán đơn giản nhất để tính hợp của tất cả các hình chữ nhật trong tập $s$ chính là duyệt qua mọi hình chữ nhật. Khi đó, độ phức tạp tổng quát của thuật toán là $O(n^2)$ : Ta duyệt qua $O(n)$ sự kiện, và với mỗi sự kiện lại duyệt qua $O(n)$ hình chữ nhật mà đường quét đang cắt qua (bao gồm cả các thao tác thêm hình chữ nhật mới - xóa hình chữ nhật cũ mà đường quét không còn cắt nữa trong tập $s$ ):

Để tối ưu thuật toán, ta sẽ cần dùng tới CTDL Segment Tree: Ta dựng cây phân đoạn với $O(n)$ đoạn thẳng con này là các nút lá. Tại mỗi nút trong cây phân đoạn ta sẽ lưu hai giá trị để trả lời cho hai câu hỏi:

Tổng độ dài các phần được ít nhất một hình chữ nhật phủ trong đoạn con mà nút quản lý là bao nhiêu?
Hiện có bao nhiêu hình chữ nhật đang phủ đoạn con mà nút quản lý?
Segment Tree luôn luôn chỉ quản lý các hình chữ nhật mà đường quét đang cắt qua, nên ở mỗi bước kết quả sẽ nằm ở gốc của cây.

Cụ thể như sau: Khi xét cạnh thứ $i,$ có hai trường hợp:

Nếu nó là cạnh bên trái của một hình chữ nhật, thì số lượng hình chữ nhật mà đường quét cắt qua sẽ tăng thêm $1,$ ngược lại thì giảm đi $1$ . Ta sẽ cập nhật giá trị tương ứng trên đoạn tọa độ $y \in [y_1, y_2 - 1]$ (do công thức sử dụng để tính độ dài phần nét liền phủ từ tọa độ $l$ tới tọa độ $r$ là $r - l + 1$ nên phải chuyển $y_2$ thành $y_2 - 1$ để thu được kết quả đúng).
Tính toán kết quả: Tổng độ dài của các phần được ít nhất một hình chữ nhật phủ trong tất cả các đoạn thẳng đang được Segment Tree quản lý sẽ luôn luôn nằm ở nút gốc của Segment Tree.

Trong trường hợp tọa độ của các đỉnh lớn hơn nữa ( $\le 10^9$ chẳng hạn), ta kết hợp thêm kĩ thuật nén số để có thể sử dụng Segment Tree.

Cài đặt

#include <bits/stdc++.h>

using namespace std;

const int maxv = 30000;

struct Seg
{
    int x, y1, y2;
    int type;

    bool operator < (const Seg& other)
    {
        return x < other.x;
    }
};

struct SegmentTree
{
    vector < pair < int, int > > s;

    SegmentTree(int n)
    {
        s.resize(4 * n + 1);
        for (int i = 0; i <= 4 * n; ++i)
            s[i] = {0, 0};
    }

    void update(int id, int l, int r, int u, int v, int val)
    {
        if (l > v || r < u)
            return;

        if (l >= u && r <= v)
        {
            s[id].second += val;

            if (s[id].second != 0)
                s[id].first = r - l + 1;
            else if (l != r)
                s[id].first = s[id * 2].first + s[id * 2 + 1].first;
            else
                s[id].first = 0;

            return;
        }

        int mid = (l + r) >> 1;
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);

        if (s[id].second != 0)
            s[id].first = r - l + 1;
        else
            s[id].first = s[id * 2].first + s[id * 2 + 1].first;
    }
};

void solution(int n, vector < Seg >& segments)
{
    sort(segments.begin(), segments.end());

    SegmentTree st(maxv);
    int res = 0;
    for (int i = 0; i < (int) segments.size() - 1; ++i)
    {
        st.update(1, 0, maxv, segments[i].y1, segments[i].y2 - 1, segments[i].type);
        res += (segments[i + 1].x - segments[i].x) * st.s[1].first;
    }

    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector < Seg > segments;
    for (int i = 1; i <= n; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // Cạnh bên trái, khi đường quét cắt vào sẽ làm tăng số HCN trong danh sách.
        segments.push_back({x1, y1, y2, 1});
        // Cạnh bên phải, khi đường quét cắt vào sẽ làm giảm số HCN trong danh sách.
        segments.push_back({x2, y1, y2, -1});
    }

    solution(n, segments);

    return 0;
}

Đánh giá

Độ phức tạp thời gian tổng quát của thuật toán là $O(n \times \log n),$ do các thao tác thêm - xóa hình chữ nhật và tìm tổng độ dài của các phần "nét liền màu xanh" đã được tối ưu xuống $O(\log n)$ với Segment Tree.

Độ phức tạp không gian tổng quát của thuật toán là $O(n)$ .

III. Bài tập tự luyện

Đường quét là một thuật toán rất mạnh trong lập trình thi đấu, các bạn nên dành thêm thời gian để tự luyện thêm dạng bài này nếu như muốn xử lý tốt các bài tập hình học trong kì thi.

Dưới đây là một số bài tập hay của dạng này: