I. Giới Thiệu
Trong hình học tính toán, việc xem xét các điểm trên mặt phẳng là một tình huống phổ biến trong giải quyết bài toán. Tuy nhiên, khi đối mặt với dữ liệu lớn trong lĩnh vực lập trình thi đấu, việc quét qua tất cả các điểm trên mặt phẳng trở nên bất khả thi. Do đó, thuật toán chỉ tập trung vào những điểm quan trọng.
Thuật toán đường quét (Sweep line algorithm) là một công cụ mạnh mẽ trong hình học tính toán, với ý tưởng cơ bản là sử dụng một đường thẳng dọc để "quét" qua mặt phẳng.
Trước khi bạn tiếp tục đọc bài viết này, hãy đảm bảo rằng bạn đã nắm vững các khái niệm sau:
- Lý thuyết khoảng cách: Đối với hai điểm P(xP, yP) và Q(xQ, yQ), chúng ta có hai loại khoảng cách:
- Khoảng cách Euclid: được tính bằng công thức Pythagoras.
- Khoảng cách Manhattan: tính bằng tổng các đoạn đường di chuyển theo chiều ngang và chiều dọc.
- Kỹ thuật hỗ trợ: Bao gồm các kỹ thuật như Hai con trỏ và Rời rạc hóa để tối ưu hóa xử lý dữ liệu.
- Cấu trúc dữ liệu hỗ trợ: Như Cây phân đoạn và Cây chỉ số nhị phân.
- Thuật toán Bao lồi: Một khái niệm quan trọng trong hình học tính toán.
Những kiến thức này sẽ được áp dụng để lọc và xử lý các điểm quan trọng trong quá trình quét trên mặt phẳng.
Bây giờ, chúng ta sẽ cùng nhau phân tích ý tưởng của thuật toán đường quét thông qua các bài toán kinh điển.
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 này được xác định bằng 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 xi, yi - tọa độ của điểm thứ i.
Ràng Buộc
- 1≤n≤50000.
- |xi|,|yi|≤106 cho mọi i: 1≤i≤n.
Output
- In 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 thập phân.
Sample Input
5
0 0
0 1
100 45
2 3
9 9Sample Output
1 2 1.000000Ý Tưởng
Việc xem xét mọi cặp điểm sẽ dẫn đến tình trạng thời gian chạy quá lâu. Tuy nhiên, thuật toán đường quét giúp cắt giảm độ phức tạp xuống O(n × log n).
Đầu tiên, ta sắp xếp các điểm theo thứ tự hoành độ, sau đó duyệt qua từng điểm trong danh sách đã sắp xếp, tìm các điểm "đáng quan tâm" để tính toán khoảng cách, giới hạn chi phí xử lý ở O(log n).
Giả sử ta đã xử lý i-1 điểm. Tại bước này, điểm i là điểm đang xét p(xi, yi). Để tìm ra cặp điểm có khoảng cách nhỏ hơn d, chúng ta chỉ cần quan tâm tới tối đa 8 điểm khác, như sau:
Bổ đề 1: Tại mỗi bước, để tìm cặp điểm nhỏ hơn d, ta chỉ cần quan tâm tới tối đa 8 điểm.
Cài Đặt Mẫu
... (bao gồm đoạn mã C++ tương tự như phần trên)
Đánh Giá
Tổng chi phí cho quá trình xử lý điểm là O(n × log n), tổng độ phức tạp thời gian là O(n × log n).
2. Bài Toán Tìm Tổng Diện Tích Bị Che Phủ Bởi Các Hình Chữ Nhật
Đề Bài
Trên mặt phẳng 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 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 x1, y1, x2, y2 biểu diễn tọa độ của các góc.
Ràng Buộc
- 1≤n≤104.
- 0≤x1≤x2≤30000 và 0≤y1≤y2≤30000.
Output
- In ra diện tích được che phủ.
Sample Input
2
10 10 20 20
15 15 25 30Sample Output
225Ý Tưởng
Thay vì xử lý từng hình chữ nhật một cách riêng lẻ, ta tách mỗi hình chữ nhật thành hai sự kiện: một cho cạnh bên trái và một cho cạnh bên phải. Bằng cách này, thuật toán đường quét cho phép ta tính toán tổng diện tích mà các hình chữ nhật này cover.
Bằng cách duy trì một structure data như Segment Tree, ta có thể tối ưu hóa việc tính toán độ dài của các phần được che phủ từ các hình chữ nhật này một cách hiệu quả.
Cài Đặt Mẫu
... (bao gồm đoạn mã C++ tương tự như phần trên)
Đánh Giá
Độ phức tạp tổng quát của thuật toán là O(n × log n), đảm bảo hiệu suất cao.
III. Bài Tập Tự Luyện
Thuật toán đường quét là một công cụ rất mạnh trong lập trình thi đấu. Bạn nên dành thời gian luyện tập thêm để thành thạo các dạng bài này.
IV. Tài Liệu Tham Khảo
source: viblo
