CTDL & giải thuật

Bao lồi Convex Hull bằng Monotone Chain

Bao lồi là dây cao su căng quanh một tập điểm. Monotone Chain sắp điểm rồi dựng nửa dưới và nửa trên bằng một quy tắc quay duy nhất.

Dây cao su quanh một tập điểm

Bao lồi là đa giác lồi nhỏ nhất chứa mọi điểm đầu vào. Hình dung đóng đinh tại các điểm rồi căng dây cao su: dây chỉ chạm các điểm ngoài cùng, còn điểm bên trong không xuất hiện trên biên. Monotone Chain dựng biên dưới và biên trên sau một lần sắp xếp.

Ý chính

Tích có hướng quyết định ba điểm rẽ trái, rẽ phải hay thẳng hàng. Bản bài loại các điểm thẳng hàng nằm giữa và chỉ giữ hai đầu cực trị của mỗi cạnh.

Convex Hull (Monotone Chain): giữ 4 đỉnh góc, loại 2 điểm Loại (1,0) và (1,1) Chuỗi dưới: (0,0) → (2,0) → (2,2) Bỏ (1,0) thẳng hàng và (1,1) rẽ phải Chuỗi trên: (2,2) → (0,2) → (0,0) Chỉ giữ các bước rẽ trái cross > 0 Kết quả CCW: 4 đỉnh góc (0,0) → (2,0) → (2,2) → (0,2)
Monotone Chain Convex Hull 1. Chuỗi dưới (Lower Hull) (0,0) → (2,0) → (2,2) 2. Quy tắc cross ≤ 0 Loại (1,0) và điểm trong (1,1) 3. Chuỗi trên (Upper Hull) (2,2) → (0,2) → (0,0) Bao lồi: 4 đỉnh góc · O(n log n)
Hình 1. Dựng chuỗi dưới và chuỗi trên bằng tích có hướng để loại điểm trong (1, 1) và điểm giữa cạnh (1, 0).

Tích chéo thay cho góc lượng giác

Với O, A, B, tính (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x). Kết quả dương nghĩa vector OA quay trái tới OB, âm là quay phải, 0 là thẳng hàng. Không cần atan2, căn bậc hai hay số thực, nên tránh sai số khi chỉ cần hướng quay.

Tọa độ có trị tuyệt đối tới 10^9 làm hiệu tọa độ tới 2·10^9, mỗi tích tới 4·10^18 và cross tới khoảng 8·10^18. C++ phải dùng long long (tối đa khoảng 9,2·10^18), và khi đó đã sát biên; nếu miền còn lớn hơn, cần __int128. Ép kiểu phải xảy ra trước phép nhân, nếu không hai số int đã tràn rồi mới được gán sang kiểu rộng.

Dựng nửa dưới

Sắp các điểm theo (x,y) và xóa trùng. Duyệt từ trái sang phải. Trước khi thêm điểm p, trong khi hai điểm cuối của hull cùng p tạo cross <=0 (chưa tạo hướng rẽ trái > 0), bỏ điểm cuối. Sau vòng này, mọi lượt quay trên nửa dưới là trái nghiêm ngặt. Thêm p rồi tiếp tục.

Tại sao được bỏ? Nếu ba điểm quay phải, điểm giữa làm biên lõm nên không thể thuộc bao lồi. Nếu thẳng hàng, điểm giữa nằm trên đoạn nối hai đầu; theo hợp đồng không giữ điểm biên trung gian, nó cũng được loại. Nếu bài muốn liệt kê mọi điểm trên cạnh, đổi dấu so sánh và xử lý trường hợp mọi điểm thẳng hàng cẩn thận.

Nửa trên được dựng bằng quy trình giống hệt nhưng duyệt danh sách đảo. Mỗi nửa chứa cả điểm trái nhất và phải nhất; khi nối, bỏ phần tử cuối của mỗi nửa để hai đầu không lặp. Kết quả bắt đầu từ điểm nhỏ nhất theo từ điển và đi ngược chiều kim đồng hồ.

Ví dụ gồm bốn góc (0,0),(2,0),(2,2),(0,2), điểm trong (1,1) và điểm giữa cạnh (1,0). Biên cuối chỉ còn bốn góc. Điểm trong bị loại bởi lượt quay; điểm giữa cạnh bị loại do cross bằng 0.

Trường hợp 0, 1, 2 điểm

Sau xóa trùng, nếu còn tối đa hai điểm, trả thẳng danh sách đã sắp. Điều này tránh nối hai nửa rồi xóa nhầm. Với nhiều điểm nhưng tất cả thẳng hàng, quy tắc <=0 (chỉ giữ lượt rẽ > 0) cũng trả hai đầu cực trị. Cần ghi rõ kết quả này vì một số đề yêu cầu mọi điểm biên.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std; using ll=long long; using P=pair<ll,ll>;
ll cross(P o,P a,P b){return (a.first-o.first)*(b.second-o.second)-(a.second-o.second)*(b.first-o.first);}
vector<P> hull(vector<P> p){sort(p.begin(),p.end());p.erase(unique(p.begin(),p.end()),p.end());if(p.size()<=2)return p;vector<P>h;for(P x:p){while(h.size()>=2&&cross(h[h.size()-2],h.back(),x)<=0)h.pop_back();h.push_back(x);}int low=h.size();for(int i=(int)p.size()-2;i>=0;--i){while((int)h.size()>low&&cross(h[h.size()-2],h.back(),p[i])<=0)h.pop_back();h.push_back(p[i]);}h.pop_back();return h;}
int main(){int n=6;vector<P>p={{0,0},{2,0},{2,2},{0,2},{1,1},{1,0}};if(cin>>n){p.resize(n);for(auto&[x,y]:p)cin>>x>>y;}auto h=hull(p);cout<<h.size()<<'\n';for(auto [x,y]:h)cout<<x<<' '<<y<<'\n';}

Sắp xếp tốn O(n log n). Trong phần dựng, mỗi điểm được đẩy vào và lấy khỏi mỗi stack nhiều nhất một lần nên O(n). Bộ nhớ O(n). Độ phức tạp không phụ thuộc kích thước tọa độ, nhưng an toàn số học thì có.

Cẩn thận

Chọn cross < 0 hay cross <= 0 làm điều kiện bỏ điểm không chỉ là chi tiết code. Nó quyết định có giữ các điểm thẳng hàng trên cạnh hay không; hãy chọn theo đúng định dạng đầu ra của đề.

Học cùng giảng viên

Chủ đề này nằm trong Buổi 14 - Geometry cơ bản + Convex Hull của Tài năng lập trình. Xem đề cương

Thứ tự đỉnh và các phép tính tiếp theo

Kết quả CCW thuận tiện cho công thức dây giày tính hai lần diện tích có dấu. Chu vi cộng khoảng cách Euclid giữa các cặp kề và cạnh đóng cuối. Đường kính đa giác lồi dùng rotating calipers sau khi đã có thứ tự vòng; không nên chạy trên tập điểm chưa sắp.

Kiểm tra điểm nằm trong đa giác lồi có thể làm O(log n) bằng cách chia quạt từ một đỉnh rồi tìm tam giác chứa. Tách nhiều lớp bao lồi lặp lại phép dựng, nhưng cách xóa điểm quyết định độ phức tạp và cách xử lý điểm biên.

Những nhầm lẫn thường gặp

Xóa trùng sau khi dựng làm các cạnh độ dài 0 phá phép quay. Quên pop_back cuối khi nối tạo đỉnh đầu lặp và có thể làm sai số đỉnh. Dùng số thực cho cross vừa chậm vừa sinh sai số không cần thiết. Một lỗi khác là cho rằng thứ tự input đã quanh biên; Monotone Chain luôn cần sắp từ điển.

Nếu đề chỉ cần diện tích bao lồi, vẫn nên kiểm số đỉnh nhỏ hơn 3 trước công thức đa giác. Nếu đề giữ điểm thẳng hàng, cần tránh việc toàn bộ dãy xuất hiện hai lần ở nửa trên và dưới.

Tự kiểm tra tính lồi và tính bao phủ trên lưới nhỏ

Khi tự kiểm tra hàm dựng bao lồi, bạn nên thử trước các bộ dữ liệu biên dễ gây lỗi: một hình vuông có thêm điểm nằm bên trong và điểm nằm giữa cạnh, tập chỉ gồm một điểm, và tập gồm nhiều điểm trùng nhau hoặc thẳng hàng. Ngoài việc so sánh trực tiếp danh sách đỉnh trên các ví dụ đã biết, bạn có thể sinh mọi tập con điểm nhỏ trên lưới 3 × 3 để kiểm tra tự động.

Một phép kiểm tra đầy đủ không chỉ nhìn vào tính chất “mọi bộ ba đỉnh liên tiếp đều rẽ trái”, vì điều kiện đó mới chứng minh đa giác đầu ra là lồi chứ chưa chứng minh nó bao hết tập điểm ban đầu. Với mỗi cạnh có hướng (u, v) trên bao lồi vừa tìm được, hãy duyệt lại toàn bộ các điểm đầu vào p và xác nhận cross(u, v, p) >= 0 (mọi điểm đều nằm bên trái hoặc nằm ngay trên đường thẳng chứa cạnh). Kết hợp cả hai điều kiện mới bảo đảm bao lồi thực sự đúng.

Kiểm một hull mà không cần biết trước đáp án

Sau khi có danh sách đỉnh, kiểm ba tính chất. Thứ nhất, không có hai đỉnh liên tiếp trùng nhau. Thứ hai, mọi bộ ba liên tiếp quay cùng chiều theo hợp đồng đã chọn. Thứ ba, mọi điểm đầu vào nằm trong hoặc trên các nửa mặt phẳng do cạnh hull xác định.

Dữ liệu Hull mong đợi
một điểm chính điểm đó
hai điểm khác nhau cả hai theo thứ tự tăng
năm điểm thẳng hàng hai đầu cực trị
hình vuông có điểm giữa bốn góc

Hãy thử mọi tập con của lưới 3×3. Không chỉ đếm số đỉnh: so cả thứ tự vòng và kiểm quy tắc có giữ điểm thẳng hàng hay không. Khi đổi điều kiện bỏ điểm từ cross <= 0 sang cross < 0 (giữ điểm thẳng hàng trên cạnh), nhớ sửa luôn đáp án mong đợi của ca thẳng hàng.

Giữ hay loại điểm thẳng hàng

Hai đầu ra đều có thể đúng tùy đề. Nếu chỉ cần các đỉnh góc, dùng cross <= 0 (chỉ giữ cross > 0) khi dựng mỗi nửa để loại điểm nằm giữa cạnh. Nếu cần mọi điểm trên biên, dùng điều kiện quay phải nghiêm ngặt, rồi xử lý riêng trường hợp toàn bộ điểm thẳng hàng để không liệt kê dãy hai lần.

Thứ tự đầu ra cũng là một phần hợp đồng. Có đề yêu cầu bắt đầu từ điểm có y nhỏ nhất, đi thuận chiều kim đồng hồ; Monotone Chain mặc định ở đây bắt đầu từ điểm nhỏ nhất theo (x,y) và đi ngược chiều. Có thể xoay vector và đảo thứ tự sau khi dựng mà không thay đổi tập đỉnh.

Khi dùng hull cho rotating calipers, hãy loại đỉnh lặp cuối và giữ hướng vòng nhất quán. Khi dùng công thức diện tích, trị tuyệt đối của tổng dây giày cho diện tích nhưng dấu vẫn hữu ích để phát hiện thứ tự CW/CCW. Những kiểm tra nhỏ này giúp các thuật toán hình học ghép với nhau ổn định.

Luyện ngay trên Big-O Coding

Bài dưới đây yêu cầu dựng bao lồi của một tập điểm, đúng phần vừa học.

Câu hỏi thường gặp

Monotone Chain khác Graham Scan thế nào?

Cả hai O(n log n). Monotone Chain sắp theo tọa độ rồi dựng hai nửa; Graham thường sắp theo góc quanh một điểm mốc.

Bao lồi có chứa điểm trên cạnh không?

Về tập hình học thì có. Danh sách đỉnh đầu ra có giữ các điểm trung gian hay không là lựa chọn cài đặt.

Có cần đóng đa giác bằng cách lặp đỉnh đầu?

Code trả mỗi đỉnh một lần. Khi duyệt cạnh, dùng (i+1)%h để nối đỉnh cuối về đầu.

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483