Giới thiệu
Bài viết này giới thiệu về Sweep Line (Thuật toán đường quét), một kỹ thuật hiệu quả trong lĩnh vực hình học máy tính. Nguyên lý cơ bản của Sweep Line là mô phỏng việc di chuyển một đường thẳng (thường là đường thẳng đứng) qua mặt phẳng để xử lý các đối tượng hình học.
Tuy nhiên, trong thực tế, việc quét liên tục qua mọi vị trí là không thể, do đó Sweep Line chỉ tập trung vào các điểm hoặc vị trí quan trọng (sự kiện) trên mặt phẳng.
Lưu ý
Một số khái niệm quan trọng sẽ được sử dụng trong suốt bài viết:
Xét hai điểm \(P(x_P, y_P)\) và \(Q(x_Q, y_Q)\):
- Khoảng cách Euclid giữa hai điểm \(P\) và \(Q\) là khoảng cách hình học thông thường, tính bằng công thức Pythagoras \(\sqrt{(x_Q – x_P)^2 + (y_Q – y_P)^2}\).
- Khoảng cách Manhattan giữa hai điểm \(P\) và \(Q\) là tổng chênh lệch tuyệt đối của tọa độ theo từng trục, tính bằng công thức: \(|x_Q – x_P| + |y_Q – y_P|\). Đây là khoảng cách di chuyển giữa hai điểm nếu chỉ được đi theo phương ngang hoặc phương dọc.
Như đã nói, áp dụng thuật toán đường quét thường đòi hỏi kết hợp với các kỹ thuật và cấu trúc dữ liệu khác để tối ưu hóa việc xử lý các điểm sự kiện quan trọng, thay vì duyệt toàn bộ mặt phẳng. Một số ví dụ bao gồm: kỹ thuật hai con trỏ, kỹ thuật rời rạc hóa tọa độ (nén số), cây phân đoạn (Segment Tree), cây Fenwick (BIT). Người đọc nên có kiến thức nền tảng về các chủ đề này để hiểu rõ hơn nội dung bài viết.
Bài toán tìm cặp điểm gần nhất
Link bài: SPOJ – CLOPPAIR
Đề bài
Cho \(n\) điểm trên mặt phẳng. Hãy xác định khoảng cách Euclid nhỏ nhất giữa hai điểm bất kỳ trong tập hợp điểm đã cho.
Giới hạn:
- \(2 \le n \le 50000\)
- Tọa độ các điểm là số nguyên \(-10^6 \le x, y \le 10^6\)
Phân tích thuật toán
Một cách tiếp cận đơn giản là tính khoảng cách giữa mọi cặp điểm, với độ phức tạp \(O(n^2)\), tuy nhiên cách này không hiệu quả với giới hạn thời gian cho phép. Sử dụng thuật toán đường quét có thể giúp giảm độ phức tạp xuống còn \(O(n \log n)\).
Đầu tiên, ta sắp xếp các điểm theo hoành độ tăng dần. Sau đó, ta duyệt qua các điểm theo thứ tự này. Điểm cải tiến so với phương pháp duyệt toàn bộ là tại mỗi điểm đang xét, ta chỉ cần xem xét một số lượng nhỏ các điểm “ứng viên” gần đó, thay vì tất cả các điểm trước đó. Việc tìm các điểm ứng viên này có thể thực hiện trong \(O(\log n)\), dẫn đến độ phức tạp tổng thể là \(O(n \log n)\).
Giả định rằng sau khi xử lý \(i-1\) điểm đầu tiên, khoảng cách nhỏ nhất tìm được là \(d\). Khi xét điểm thứ \(i\), ký hiệu là \(P\), ta chỉ cần tìm các điểm \(Q\) (với \(Q\) đã được xử lý trước đó) sao cho khoảng cách giữa \(P\) và \(Q\) nhỏ hơn \(d\).
Bổ đề 1
Tại mỗi bước của thuật toán, để tìm một cặp điểm có khoảng cách nhỏ hơn \(d\), ta chỉ cần xem xét tối đa \(8\) điểm khác trong số các điểm đã xử lý.
Chứng minh
Từ \(P\), kẻ 8 hình vuông kề nhau, mỗi hình vuông có cạnh \(d/2\), tâm tại \(P\), như hình minh họa (điểm \(P\) là điểm màu xanh).
Do các điểm được duyệt theo thứ tự hoành độ tăng dần, tất cả \(i-1\) điểm đã xử lý đều nằm bên trái hoặc trên cùng đường thẳng đứng với \(P\). Ta chỉ cần quan tâm đến những điểm \(Q\) đã xử lý mà nằm trong hình chữ nhật kích thước \(d \times 2d\) bên trái \(P\) (vì nếu \(|x_P – x_Q| > d\) hoặc \(|y_P – y_Q| > d\) thì khoảng cách Euclid chắc chắn lớn hơn \(d\)). Chia hình chữ nhật này thành 8 ô vuông cạnh \(d/2\). Vì \(d\) là khoảng cách nhỏ nhất tìm được cho đến nay giữa các điểm đã xử lý, mỗi ô vuông \(d/2 \times d/2\) chỉ có thể chứa tối đa một điểm trong số \(i-1\) điểm đầu tiên. Do đó, có tối đa 8 điểm cần xem xét trong vùng này để cập nhật khoảng cách \(d\).
Từ bổ đề 1, ta thấy rằng cần quản lý một tập hợp \(S\) chứa các điểm “hoạt động” – những điểm có hoành độ \(x\) sao cho \(x_P – x \le d\). Vì các điểm được duyệt theo thứ tự hoành độ tăng dần và \(d\) có thể giảm, việc loại bỏ các điểm cũ khỏi \(S\) (những điểm có \(x_P – x > d\)) có thể thực hiện hiệu quả (ví dụ, bằng kỹ thuật hai con trỏ). Ngoài ra, để nhanh chóng tìm các điểm \(Q \in S\) thỏa mãn \(|y_P – y_Q| \le d\), tập \(S\) cần được sắp xếp theo tung độ. Cấu trúc dữ liệu std::set (hoặc cây cân bằng) có thể đáp ứng yêu cầu này.
Các bước cụ thể của thuật toán:
- Sắp xếp các điểm theo hoành độ \(x\).
- Khởi tạo khoảng cách nhỏ nhất \(d\) bằng khoảng cách giữa hai điểm đầu tiên.
- Duy trì một tập \(S\) (ví dụ:
std::set) lưu trữ các điểm hoạt động, sắp xếp theo tung độ \(y\). - Dùng một con trỏ `left_idx` để theo dõi chỉ số của điểm xa nhất bên trái mà vẫn còn trong khoảng \(d\) so với điểm hiện tại.
- Duyệt qua từng điểm \(P_i\) (với \(i\) từ 2 đến \(n-1\)):
- Loại bỏ các điểm \(P_j\) (với \(j < left\_idx\)) khỏi \(S\) nếu \(x_i – x_j > d\), cập nhật `left_idx`.
- Tìm trong \(S\) các điểm \(Q\) có tung độ nằm trong khoảng \([y_i – d, y_i + d]\).
- Với mỗi điểm \(Q\) tìm được, tính khoảng cách \(dist(P_i, Q)\) và cập nhật \(d\) (và cặp điểm tương ứng) nếu \(dist(P_i, Q) < d\).
- Thêm \(P_i\) vào tập \(S\).
Mỗi điểm được thêm và xóa khỏi \(S\) tối đa một lần, mỗi thao tác mất \(O(\log n)\). Việc tìm kiếm các điểm trong khoảng tung độ \([y_i – d, y_i + d]\) trong \(S\) cũng mất \(O(\log n)\). Theo Bổ đề 1, số lượng điểm \(Q\) cần kiểm tra là hằng số. Do đó, độ phức tạp tổng thể là \(O(n \log n)\).
Cài đặt mẫu
Trong phần cài đặt này, các khoảng cách được lưu dưới dạng bình phương để tránh sai số do căn bậc hai.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Point{
ll 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) const {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
};
int n;
vector points; // Vector chứa tất cả các điểm
set<Point, cmp> T;
ll squared_dist(Point a, Point b) { // Nhận vào hai điểm, trả vể
// bình phương khoảng cách giữa hai điểm
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) { ll x, y; cin >> x >> y;
points.push_back({x, y, i});
}
ll squared_d = squared_dist(points[0], points[1]); // Lưu bình phương của d
int res_id1 = 0, res_id2 = 1;
sort(points.begin(), points.end()); // Sắp xếp các điểm theo hoành độ
for (auto p : points) {
ll x = p.x, y = p.y;
int id = p.id;
ll d = sqrt(squared_d);
Point cur = {-1000001, y - d, id};
while (1) { // Tìm tất cả các điểm có tung độ trong khoảng [y - d, y + d]
auto it = T.upper_bound(cur);
if (it == T.end()) break;
cur = *it;
if (cur.y > y + d) break; // Dừng lại nếu điểm có tung độ lớn hơn y + d
if (cur.x < x - d) {
T.erase(it);
continue;
} // Xóa điểm nếu điểm này có hoành độ bé hơn x - d
if (squared_dist(p, cur) < squared_d) { squared_d = squared_dist(p, cur); res_id1 = id; res_id2 = cur.id; } // Gán đáp án mới nếu tìm được d nhỏ hơn } T.insert(p); // Thêm điểm hiện tại vào T } if (res_id1 > res_id2) swap(res_id1, res_id2);
cout << res_id1 << " " << res_id2 << " ";
cout << fixed << setprecision(6) << sqrt(squared_d);
}
Bài toán tìm giao điểm của các đoạn thẳng song song với trục toạ độ
Link bài: SPOJ – CS345A1
Đề bài
Cho một tập hợp các đoạn thẳng, mỗi đoạn thẳng song song với trục \(Ox\) (đoạn ngang) hoặc trục \(Oy\) (đoạn dọc). Hãy đếm tổng số giao điểm giữa các đoạn thẳng ngang và đoạn thẳng dọc.
Giới hạn:
- \(1 \le n \le 100000\)
- Tọa độ \(x\), \(y\) của mỗi điểm là số thực thỏa mãn \(0 \le x_1, y_1, x_2, y_2 \le 30000\)
Phân tích thuật toán
Tương tự bài toán trước, ta có thể áp dụng ý tưởng đường quét.
Vấn đề là các đoạn thẳng ngang kéo dài trên một khoảng hoành độ, gây khó khăn cho việc xác định thứ tự xử lý. Để khắc phục, ta biểu diễn mỗi đoạn thẳng ngang bằng hai sự kiện: một sự kiện “bắt đầu” tại đầu mút bên trái và một sự kiện “kết thúc” tại đầu mút bên phải. Các đoạn thẳng dọc được xem là các sự kiện đơn tại hoành độ của chúng. Tập hợp các sự kiện bao gồm:
- Sự kiện bắt đầu của đoạn ngang: thêm đoạn thẳng vào trạng thái quét.
- Sự kiện kết thúc của đoạn ngang: xóa đoạn thẳng khỏi trạng thái quét.
- Sự kiện đoạn thẳng dọc: truy vấn các đoạn ngang đang hoạt động.
Sau đó, ta sắp xếp tất cả các sự kiện này theo hoành độ tăng dần.
Ta di chuyển đường quét từ trái qua phải theo các sự kiện đã sắp xếp. Ta duy trì một cấu trúc dữ liệu (gọi là \(S\)) lưu trữ các tung độ \(y\) của các đoạn thẳng ngang đang được đường quét cắt qua (đang “hoạt động”).
Khi gặp một sự kiện:
- Nếu là sự kiện bắt đầu của đoạn ngang tại \((x, y)\): Thêm \(y\) vào cấu trúc dữ liệu \(S\).
- Nếu là sự kiện kết thúc của đoạn ngang tại \((x, y)\): Xóa \(y\) khỏi cấu trúc dữ liệu \(S\).
- Nếu là đoạn thẳng dọc \(v_i\) tại hoành độ \(x\) nối từ \(y_1\) đến \(y_2\): Truy vấn cấu trúc dữ liệu \(S\) để đếm số lượng tung độ \(y\) đang hoạt động thỏa mãn \(y_1 \le y \le y_2\). Cộng số lượng này vào tổng số giao điểm.
Cấu trúc dữ liệu \(S\) cần hỗ trợ hiệu quả các thao tác: thêm giá trị, xóa giá trị, và đếm số lượng giá trị trong một khoảng. Do tọa độ có thể là số thực hoặc nằm trong khoảng lớn, ta sử dụng kỹ thuật rời rạc hóa (nén số) cho các giá trị tung độ. Sau khi rời rạc hóa, các tung độ sẽ nằm trong khoảng \([1, M]\) với \(M = O(n)\). Khi đó, ta có thể dùng cây Fenwick (BIT) hoặc cây Segment Tree để thực hiện các thao tác trên trong \(O(\log n)\) hoặc \(O(\log M)\).
Độ phức tạp thời gian tổng thể là \(O(n \log n)\) do việc sắp xếp sự kiện và các thao tác trên cây Fenwick/Segment Tree. Độ phức tạp bộ nhớ là \(O(n)\).
Minh họa thuật toán:
Cài đặt mẫu
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const double EPS = 1e-9;
struct Event{
double x;
int y, y2, type;
bool operator < (const Event& other) const {
return x < other.x;
}
};
struct FenwickTree{
int n;
vector s;
FenwickTree(int n) : n(n), s(n + 5) {
for (int i = 1; i <= n; i++) s[i] = 0;
}
void update(int i, int val) {
for (; i <= n; i += i & -i) s[i] += val;
}
int getsum(int i) {
int res = 0;
for (; i; i -= i & -i) res += s[i];
return res;
}
int query(int l, int r) {
return getsum(r) - getsum(l - 1);
}
};
int n;
double blue_x1[N], blue_x2[N], blue_y[N], red_y1[N], red_y2[N], red_x[N];
vector compress_y;
vector events;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) { cin >> blue_x1[i] >> blue_x2[i] >> blue_y[i];
if (blue_x1[i] > blue_x2[i]) swap(blue_x1[i], blue_x2[i]);
compress_y.push_back(blue_y[i]);
}
for (int i = 1; i <= n; i++) { cin >> red_y1[i] >> red_y2[i] >> red_x[i];
if (red_y1[i] > red_y2[i]) swap(red_y1[i], red_y2[i]);
compress_y.push_back(red_y1[i]);
compress_y.push_back(red_y2[i]);
}
sort(compress_y.begin(), compress_y.end());
compress_y.erase(unique(compress_y.begin(), compress_y.end()), compress_y.end());
// Rời rạc hóa các tung độ
for (int i = 1; i <= n; i++) {
int yy = lower_bound(compress_y.begin(), compress_y.end(), blue_y[i]) - compress_y.begin() + 1;
events.push_back({blue_x1[i] - EPS, yy, 0, 1}); // Phần tử loại 1
events.push_back({blue_x2[i] + EPS, yy, 0, 2}); // Phần tử loại 2
}
for (int i = 1; i <= n; i++) {
int l = lower_bound(compress_y.begin(), compress_y.end(), red_y1[i]) - compress_y.begin() + 1;
int r = lower_bound(compress_y.begin(), compress_y.end(), red_y2[i]) - compress_y.begin() + 1;
events.push_back({red_x[i], l, r, 3}); // Phần tử loại 3
}
sort(events.begin(), events.end());
FenwickTree FT(n * 3); // Có tối đa n * 3 tung độ khác nhau
ll res = 0;
for (auto e : events) {
if (e.type == 1) FT.update(e.y, 1);
else if (e.type == 2) FT.update(e.y, -1);
else res += FT.query(e.y, e.y2);
}
cout << res;
}
Bài toán tính diện tích hợp của các hình chữ nhật
Link bài: VNOJ – AREA
Đề bài
Cho \(n\) hình chữ nhật trên mặt phẳng tọa độ, với các cạnh song song với các trục. Hãy tính diện tích hợp của \(n\) hình chữ nhật này.
Giới hạn:
- \(1 \le n \le 30000\)
- Mỗi hình chữ nhật có tọa độ góc trái dưới và góc phải trên lần lượt là \(x_1\), \(y_1\) và \(x_2\), \(y_2\) sao cho \(0 \le x_1, y_1, x_2, y_2 \le 30000\)
Phân tích
Tương tự bài toán trước, ta biểu diễn mỗi hình chữ nhật bằng hai sự kiện: một sự kiện tại cạnh trái (loại “bắt đầu”) và một sự kiện tại cạnh phải (loại “kết thúc”). Ta sắp xếp các sự kiện này theo hoành độ \(x\).
Ta quét đường thẳng đứng từ trái sang phải. Khi di chuyển từ sự kiện tại \(x_i\) đến sự kiện tiếp theo tại \(x_{i+1}\), ta cần tính diện tích của phần hợp các hình chữ nhật trong “dải” dọc có chiều rộng \((x_{i+1} – x_i)\). Diện tích này bằng \((x_{i+1} – x_i)\) nhân với tổng độ dài theo chiều dọc của đường quét (tại hoành độ bất kỳ giữa \(x_i\) và \(x_{i+1}\)) được phủ bởi ít nhất một hình chữ nhật đang “hoạt động”.
Bài toán quy về việc tính hiệu quả tổng độ dài theo trục \(y\) được phủ bởi các đoạn thẳng \(y\) tương ứng với các hình chữ nhật đang hoạt động khi đường quét di chuyển giữa hai sự kiện. Đây là bài toán “Union Length of Intervals” trên trục \(y\).
Ta có thể giải bài toán con này bằng cách sử dụng cây phân đoạn (Segment Tree) kết hợp với rời rạc hóa tọa độ. Trước tiên, ta thu thập tất cả các tung độ \(y_1, y_2\) của các hình chữ nhật và rời rạc hóa chúng thành \(O(n)\) điểm \(y’_1, y’_2, …, y’_m\). Các điểm này chia trục tung thành \(O(n)\) đoạn cơ sở \([y’_j, y’_{j+1}]\). Ta xây dựng cây phân đoạn trên các đoạn cơ sở này.
Mỗi nút trên cây phân đoạn sẽ quản lý một khoảng tung độ \([y’_a, y’_b]\) và lưu hai thông tin:
count: Số lượng hình chữ nhật đang hoạt động mà phủ hoàn toàn khoảng \([y’_a, y’_b]\).covered_length: Tổng độ dài của các đoạn cơ sở con trong \([y’_a, y’_b]\) được phủ bởi ít nhất một hình chữ nhật đang hoạt động.
Khi gặp sự kiện cạnh trái của hình chữ nhật \([x_1, x_2] \times [y_1, y_2]\) tại \(x_1\), ta cập nhật cây phân đoạn bằng cách tăng count cho các nút tương ứng với khoảng \([y_1, y_2)\) (sau khi rời rạc hóa) lên 1. Khi gặp sự kiện cạnh phải tại \(x_2\), ta giảm count tương ứng đi 1.
Việc cập nhật covered_length: Nếu count của một nút > 0, thì covered_length của nút đó bằng độ dài khoảng nó quản lý. Nếu count = 0, thì covered_length bằng tổng covered_length của hai nút con. Giá trị covered_length của nút gốc chính là tổng độ dài theo trục \(y\) đang được phủ.
Tại mỗi khoảng \([x_i, x_{i+1}]\), diện tích đóng góp vào kết quả là \( (x_{i+1} – x_i) \times \text{covered\_length}(\text{nút gốc})\). Tổng các diện tích này là kết quả cuối cùng. Độ phức tạp thời gian là \(O(n \log n)\) do sắp xếp và các thao tác trên cây phân đoạn.
Minh họa thuật toán :
Cài đặt mẫu
#include <bits/stdc++.h>
using namespace std;
const int MX = 30000;
struct Segment{
int x, y1, y2, type;
bool operator < (const Segment& other) const {
return x < other.x;
}
};
struct SegmentTree{
vector<pair<int, int>> s;
SegmentTree(int n) : s(n * 4 + 5) {
for (int i = 1; i <= 4 * n; i++) s[i] = {0, 0}; } void update(int id, int l, int r, int tl, int tr, int val) { if (l > tr || r < tl) return; if (l >= tl && r <= tr) { 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 m = (l + r) >> 1;
update(id * 2, l, m, tl, tr, val);
update(id * 2 + 1, m + 1, r, tl, tr, 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;
}
};
int n;
vector segments;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
segments.push_back({x1, y1, y2, 1});
segments.push_back({x2, y1, y2, -1});
}
sort(segments.begin(), segments.end());
SegmentTree ST(MX);
int res = 0;
for (int i = 0; i < (int)segments.size() - 1; i++) {
ST.update(1, 0, MX, segments[i].y1, segments[i].y2 - 1, segments[i].type);
res += (segments[i + 1].x - segments[i].x) * ST.s[1].first;
}
cout << res;
}
Bài toán tìm cây khung Manhattan nhỏ nhất
Link bài: Kattis – GRIDMST
Đề bài
Cho \(n\) điểm trên mặt phẳng. Xây dựng một đồ thị đầy đủ với các điểm này là đỉnh, và trọng số cạnh giữa hai điểm bằng khoảng cách Manhattan của chúng. Yêu cầu tìm tổng trọng số của cây khung nhỏ nhất (MST) của đồ thị này.
Giới hạn:
- \(1 \le n \le 100000\)
- \(n\) dòng, mỗi dòng 2 số nguyên \(x\), \(y\) sao cho \(0 \le x, y \le 100000\) là toạ độ mỗi điểm.
Phân tích
Nếu ta có thể giảm số lượng cạnh cần xem xét xuống \(O(n)\) thay vì \(O(n^2)\) cạnh của đồ thị đầy đủ, ta có thể áp dụng các thuật toán MST chuẩn như Kruskal hoặc Prim để giải bài toán trong thời gian \(O(n \log n)\).
Bổ đề 2
Xét một điểm \(P\) bất kỳ. Chia mặt phẳng thành 8 vùng (phần tám) bởi các đường thẳng \(x=x_P\), \(y=y_P\), \(y=x+(y_P-x_P)\), và \(y=-x+(y_P+x_P)\). Với mỗi vùng, xét cạnh nối \(P\) với điểm \(Q\) trong vùng đó (nếu có) sao cho khoảng cách Manhattan \(d(P, Q)\) là nhỏ nhất. Tập hợp tất cả các cạnh như vậy tạo thành từ mọi điểm \(P\) chứa ít nhất một cây khung nhỏ nhất của đồ thị đầy đủ ban đầu.
Chứng minh
Ta sẽ chứng minh bằng phản chứng rằng mọi cạnh \((u, v)\) trong một cây khung nhỏ nhất \(S\) bất kỳ đều thuộc tập cạnh được xây dựng như trên. Giả sử \((u, v) \in S\) nhưng \(v\) không phải là điểm gần \(u\) nhất theo khoảng cách Manhattan trong vùng chứa \(v\) (so với \(u\)). Điều này có nghĩa là tồn tại một điểm \(w\) trong cùng vùng đó sao cho \(d(u, w) < d(u, v)\). Do tính chất của các vùng và khoảng cách Manhattan, ta cũng có \(d(v, w) < d(u, v)\) (vì cả \(v\) và \(w\) đều “gần” \(u\) hơn là “gần” nhau theo hướng đó). Bây giờ xét chu trình tạo bởi việc thêm cạnh \((u, w)\) vào cây \(S\). Cạnh \((u, v)\) là cạnh có trọng số lớn nhất trên chu trình này (vì \(d(u,w) < d(u,v)\) và mọi cạnh khác trên đường đi từ \(u\) đến \(v\) trong \(S\) đều phải nhỏ hơn hoặc bằng \(d(u,v)\) do tính chất của MST). Do đó, ta có thể loại bỏ cạnh \((u, v)\) và thêm cạnh \((u, w)\) để tạo ra một cây khung mới có tổng trọng số nhỏ hơn, điều này mâu thuẫn với giả thiết \(S\) là cây khung nhỏ nhất. Vậy, cạnh \((u, v)\) phải là cạnh nối \(u\) với điểm gần nhất trong vùng chứa \(v\).
Từ bổ đề 2, bài toán chuyển thành tìm hiệu quả đồ thị \(G\). Điều này yêu cầu với mỗi điểm \(P\), ta phải tìm điểm gần nhất theo khoảng cách Manhattan trong mỗi 8 phần tám xung quanh nó. Ta sẽ trình bày thuật toán tìm điểm gần nhất trong phần tám thứ nhất (các điểm \(Q\) thỏa mãn \(x_Q \ge x_P\) và \(|y_Q – y_P| \le x_Q – x_P\)); các phần tám khác có thể xử lý tương tự bằng cách xoay hoặc đối xứng hệ tọa độ.
Bổ để 3
Gọi \(d(P, Q)\) là khoảng cách Manhattan giữa hai điểm \(P\) và \(Q\). Gọi \(A(x_A, y_A)\), \(B(x_B, y_B)\), \(C(x_C, y_C)\) là ba điểm trên mặt phẳng sao cho \(B, C\) cùng thuộc phần tám thứ nhất so với \(A\), và \(d(A, C) \le d(A, B)\). Khi đó, ta có \(x_C – y_C \ge x_B – y_B\). (Lưu ý: Có một sự nhầm lẫn nhỏ trong bổ đề gốc, điều kiện đúng phải là \(x_C-y_C \ge x_B-y_B\) thay vì \(x_C \ge x_B, y_C \le y_B\))
Chứng minh
Vì \(B, C\) thuộc phần tám thứ nhất của \(A\), ta có \(x_B \ge x_A, x_C \ge x_A\) và \(|y_B-y_A| \le x_B-x_A, |y_C-y_A| \le x_C-x_A\). Do đó, \(d(A,B) = (x_B-x_A) + |y_B-y_A|\) và \(d(A,C) = (x_C-x_A) + |y_C-y_A|\).
Khoảng cách Manhattan từ \(A\) đến một điểm \(P\) trong vùng này được tối thiểu hóa khi \(x_P-y_P\) được tối thiểu hóa (nếu \(y_P \ge y_A\)) hoặc \(x_P+y_P\) được tối thiểu hóa (nếu \(y_P \le y_A\)). Xét trường hợp \(y_P \ge y_A\), ta cần tìm điểm \(Q\) sao cho \(x_Q-y_Q\) là nhỏ nhất. Bổ đề 3 (phiên bản đã sửa) giúp giới hạn việc tìm kiếm.
Ta có thể sử dụng Sweep Line kết hợp với cấu trúc dữ liệu (như cây Segment Tree hoặc set) để tìm điểm gần nhất trong mỗi vùng cho mọi điểm. Một cách tiếp cận khác hiệu quả hơn là sử dụng thuật toán chia để trị kết hợp với đường quét:
- Sắp xếp các điểm theo tọa độ \(x\).
- Chia tập điểm thành hai nửa \(L\) và \(R\) bằng một đường thẳng đứng.
- Giải đệ quy cho \(L\) và \(R\).
- Tìm các cạnh nối giữa \(L\) và \(R\) thuộc đồ thị \(G\) cần thiết để đảm bảo tính liên thông và tối ưu. Bước này có thể thực hiện bằng một thuật toán sweep line trên dải giao nhau giữa \(L\) và \(R\), tương tự như bài toán cặp điểm gần nhất, nhưng sử dụng khoảng cách Manhattan và giới hạn tìm kiếm theo các vùng bát phân. Cụ thể, để tìm các cạnh từ \(L\) sang \(R\) cho vùng 1, ta sắp xếp các điểm trong dải theo \(y\), quét từ dưới lên, và dùng cấu trúc dữ liệu để tìm điểm trong \(R\) tối thiểu hóa \(x-y\).
Một phương pháp khác trực tiếp hơn để xây dựng đồ thị \(G\) là sử dụng đường quét cho cả 8 hướng. Ví dụ, để tìm các cạnh cho vùng 1 (hướng Đông-Đông-Bắc):
- Biến đổi tọa độ: \((x’, y’) = (x-y, x+y)\). Việc này xoay hệ trục 45 độ. Trong hệ tọa độ mới, khoảng cách Manhattan giữa \(P\) và \(Q\) thuộc vùng 1 của \(P\) trở thành \(x_Q – x_P\). Bài toán trở thành tìm điểm \(Q\) trong vùng tương ứng sao cho \(x_Q\) nhỏ nhất.
- Sắp xếp các điểm theo tọa độ \(x’\) (tức \(x-y\)).
- Quét các điểm theo thứ tự \(x’\) tăng dần. Sử dụng một cấu trúc dữ liệu (ví dụ: cây Fenwick hoặc Segment Tree) hoạt động trên tọa độ \(y’\) (tức \(x+y\)) để duy trì các điểm đã quét.
- Với mỗi điểm \(P\) đang xét, truy vấn cấu trúc dữ liệu để tìm điểm \(Q\) đã quét có \(y’_Q \ge y’_P\) và \(y’_Q\) nhỏ nhất. Điểm này ứng với điểm gần nhất theo \(x\) trong hệ tọa độ cũ, và do đó gần nhất theo Manhattan trong vùng 1. Thêm cạnh \((P, Q)\) vào danh sách cạnh.
- Thêm \(P\) vào cấu trúc dữ liệu.
Lặp lại quá trình này cho 8 vùng (bằng cách biến đổi tọa độ phù hợp). Tổng cộng ta thu được \(O(n)\) cạnh tiềm năng. Cuối cùng, chạy thuật toán Kruskal trên các cạnh này để tìm MST. Độ phức tạp tổng thể là \(O(n \log n)\).
Cài đặt mẫu
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
struct Point {
int x, y, id;
int diff_yx() const { return y - x; }
int sum_xy() const { return x + y; }
};
int manhattan_dist(const Point& u, const Point& v) {
return abs(u.x - v.x) + abs(u.y - v.y);
}
struct DSU {
vector par;
DSU() {}
DSU(int n): par(n, -1) {}
int find_set(int u) {
return par[u] < 0 ? u : par[u] = find_set(par[u]);
}
bool join(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u == v) return false;
if (-par[u] < -par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
};
struct Edge {
int u, v, cost;
};
bool operator<(const Edge& u, const Edge& v) {
return u.cost < v.cost;
}
Edge edge_from_point(const Point& u, const Point& v) {
return {u.id, v.id, manhattan_dist(u, v)};
}
vector potential_edges; // Các cạnh tối ưu cần xét
vector solve_single_recur(vector p) {
if (p.size() <= 1) return p;
int upper_size = (int)p.size() / 2;
auto upper = solve_single_recur({p.begin(), p.begin() + upper_size});
auto lower = solve_single_recur({p.begin() + upper_size, p.end()});
vector res;
Point min_diff_yx{0, INF, -1};
int upper_ptr = 0;
for (auto lo : lower) {
while (upper_ptr < upper_size and upper[upper_ptr].sum_xy() <= lo.sum_xy()) { if (min_diff_yx.diff_yx() > upper[upper_ptr].diff_yx()) {
min_diff_yx = upper[upper_ptr];
}
res.push_back(upper[upper_ptr]);
++upper_ptr;
}
if (min_diff_yx.id != -1) {
potential_edges.push_back(edge_from_point(min_diff_yx, lo));
}
res.push_back(lo);
}
res.insert(res.end(), upper.begin() + upper_ptr, upper.end());
return res;
}
void solve_single(vector p) { // Giải bài toán với một góc phần tám
sort(p.begin(), p.end(), [](const Point& u, const Point& v) {
return u.y == v.y ? u.x < v.x : u.y > v.y;
});
solve_single_recur(p);
}
void rotate_90(vector& p) { // Xoay tất cả các điểm 90 độ
for (auto& cur: p) {
int x = cur.x, y = cur.y;
cur.x = -y;
cur.y = x;
}
}
void flip(vector& p) { // Đối xứng các điểm qua trục Ox
for (auto& cur: p) {
cur.y = -cur.y;
}
}
int solve(vector p) {
for (int ft = 0; ft < 2; ++ft) {
for (int i = 0; i < 4; ++i) { solve_single(p); rotate_90(p); } flip(p); } int ans = 0; DSU dsu((int)p.size()); sort(potential_edges.begin(), potential_edges.end()); for (const auto& e : potential_edges) { if (dsu.join(e.u, e.v)) { ans += e.cost; } } // Thuật toán kruskal return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n;
vector p(n);
for (int i = 0; i < n; ++i) { cin >> p[i].x >> p[i].y;
p[i].id = i;
}
cout << solve(p);
}Bài tập ví dụ
Kết
Tương tự như quy hoạch động, Sweep Line không phải là một thuật toán đơn lẻ mà là một kỹ thuật thiết kế thuật toán mạnh mẽ. Nó có thể được áp dụng để giải quyết nhiều bài toán hình học đa dạng, kể cả những bài toán chưa được đề cập ở đây (ví dụ: phép triangulasi Delaunay) hoặc các bài toán mới xuất hiện trong các kỳ thi lập trình.
Tham khảo
