Giới Thiệu
Bài viết này sẽ giúp bạn hiểu rõ về Bao lồi (Convex Hull) và các thuật toán tìm kiếm nó, cùng với các khái niệm cơ bản trong Hình học tính toán. Để theo dõi nội dung, bạn nên có kiến thức về vector và giao điểm của các đường thẳng.
Định Nghĩa Bao Lồi
Bao lồi là đa giác nhỏ nhất chứa tất cả các điểm trong một tập điểm trên mặt phẳng Oxy. Giả sử bạn có một tập hợp n điểm, bao lồi tập hợp đó là đa giác nhỏ nhất theo diện tích, thể tích (tùy trường hợp sử dụng). Bạn có thể tưởng tượng rằng nếu mỗi điểm là một chiếc đinh trên tấm gỗ, bao lồi sẽ là hình dáng của tấm gỗ khi được kéo căng bởi một sợi dây nhím.
Bài toán Bao Lồi Có Thể Nêu Ra Như Sau:
Cho n điểm trên mặt phẳng toạ độ Oxy, điểm thứ i có tọa độ (x_i, y_i), hãy tìm ra các điểm tạo thành bao lồi của tập n điểm này?
Input:
- Dòng đầu tiên chứa số nguyên dương n.
- Trên n dòng kế tiếp, mỗi dòng chứa hai số nguyên x_i, y_i.
Ràng buộc:
- 1 ≤ n ≤ 100000
- |x_i|, |y_i| ≤ 10^9, với mọi i: 1 ≤ i ≤ n
Output:
- In ra các điểm thuộc bao lồi theo chiều kim đồng hồ, mỗi điểm trên một dòng gồm hoành độ và tung độ.
Ví dụ
Input:
6
2 1
1 3
2 3
2 4
4 1
4 3Output:
1 3
2 4
4 3
4 1
2 1Các Thuật Toán Tìm Bao Lồi Thông Dụng
1. Thuật Toán Graham Scan
Ý Tưởng
Thuật toán Graham được phát triển bởi Ronald Graham vào năm 1972. Ý tưởng chính là tìm đỉnh bao lồi bằng cách sắp xếp các điểm theo góc với một điểm gốc. Sau khi sắp xếp, ta sử dụng một vectơ để lưu lại đường đi của các đỉnh bao lồi.
Cài Đặt
cpp
#include <bits/stdc++.h>
// ...
// Các cấu trúc, hàm hỗ trợ khác
// ...
vector<Point> convex_hull(const int& n, vector<Point>& p, bool include_collinear = false) {
// Logic của thuật toán
}
int main() {
// Đọc dữ liệu và gọi hàm convex_hull
}2. Thuật Toán Chuỗi Đơn Điệu (Andrew's Monotone Chain)
Ý Tưởng
Thuật toán này dựa trên việc xây dựng hai chuỗi bao lồi: chuỗi trên và chuỗi dưới. Ta sẽ xác định các điểm trái nhất và phải nhất làm mốc, sau đó phân chia các điểm thành hai nhóm.
Cài Đặt
cpp
#include <bits/stdc++.h>
// ...
// Logic tương tự với Graham nhưng khác ở cách sắp xếp và xử lý
}Bài Tập Thực Hành
1. Tính Diện Tích Bao Lồi
Cho một dãy số nguyên a với n phần tử, xây dựng các điểm dạng (a_i, a_j), và yêu cầu tính 2×Area(C) của bao lồi.
2. Tìm Tam Giác Có Diện Tích Lớn Nhất
Cho n điểm trên mặt phẳng, xác định ba điểm sao cho tạo thành tam giác lớn nhất có thể.
Kết Luận
Hai thuật toán tìm bao lồi phổ biến là Graham Scan và Monotone Chain đều có độ phức tạp thời gian O(n log n), giúp giải quyết nhanh chóng bài toán tìm bao lồi trong các tình huống thực tế.
source: viblo
