Convex Hull (Bao lồi)

Bao lồi (convex hull) của một tập điểm $P$ trên mặt phẳng là đa giác lồi nhỏ nhất chứa toàn bộ các điểm của $P$. Hình dung trực quan: đóng một cái đinh ở mỗi điểm rồi căng một sợi dây thun bao quanh tất cả — khi buông tay, sợi dây ôm sát các đinh ngoài cùng và tạo thành bao lồi.

Bài toán dựng bao lồi có thể giải ngây thơ bằng cách thử mọi cạnh ứng viên trong $O(N^3)$, nhưng thuật toán Andrew's Monotone Chain (chuỗi đơn điệu của Andrew) dựng được bao lồi trong $O(N\log N)$ — gần như chỉ tốn thời gian sắp xếp. Bao lồi là nền tảng cho hàng loạt bài toán hình học: tìm cặp điểm xa nhất, kiểm tra điểm nằm trong đa giác, diện tích/chu vi nhỏ nhất bao quanh, và kỹ thuật Convex Hull Trick trong quy hoạch động.

Ý tưởng / Trực giác

Tích chéo — viên gạch nền

Mọi thứ dựa trên tích chéo (cross product). Với ba điểm $O,A,B$:

$$\text{cross}(O,A,B)=(A_x-O_x)(B_y-O_y)-(A_y-O_y)(B_x-O_x)$$

Đây là tích chéo của hai vector $\overrightarrow{OA}$ và $\overrightarrow{OB}$. Dấu của nó cho biết hướng rẽ khi đi từ $O\to A\to B$:

• $\text{cross}>0$: ba điểm rẽ trái (ngược chiều kim đồng hồ — counter-clockwise, CCW).
• $\text{cross}<0$: rẽ phải (cùng chiều kim đồng hồ — clockwise, CW).
• $\text{cross}=0$: ba điểm thẳng hàng (collinear).

Một đa giác là lồi khi đi dọc biên ta luôn rẽ về cùng một phía. Đó chính là điều kiện ta sẽ ép buộc khi xây bao lồi.

Vì sao Monotone Chain đúng

Ý tưởng: sắp xếp tất cả điểm theo $x$ tăng dần (đồng $x$ thì theo $y$). Sau khi sắp, bao lồi tách thành hai phần:

• Bao dưới (lower hull): đường biên dưới, quét từ điểm trái nhất sang điểm phải nhất.
• Bao trên (upper hull): đường biên trên, quét ngược lại từ phải sang trái.

Ghép hai phần lại được toàn bộ đa giác lồi.

Để dựng bao dưới, ta dùng một ngăn xếp (stack) và thêm từng điểm theo thứ tự đã sắp. Trước khi đẩy điểm mới $p$ vào, ta kiểm tra: nếu hai điểm trên cùng của stack cộng với $p$ tạo ra một cú rẽ không hợp lệ (không rẽ trái), thì điểm áp chót là một "chỗ lõm" — nó không thể nằm trên bao lồi, ta pop nó ra. Lặp đến khi cú rẽ hợp lệ rồi mới đẩy $p$.

Tại sao đúng? Vì các điểm đã được sắp theo $x$, khi đi từ trái sang phải mà gặp một cú rẽ sai hướng nghĩa là điểm giữa bị "ăn vào trong" — không thể là đỉnh ngoài cùng của một đa giác lồi. Loại bỏ nó không làm mất điểm nào (điểm bị loại vẫn nằm trong phần đa giác còn lại). Mỗi điểm được đẩy vào stack đúng một lần và bị pop nhiều nhất một lần, nên tổng công việc là tuyến tính sau khi sắp xếp.

Ví dụ chạy tay

Xét 6 điểm: $A(0,0),B(1,1),C(2,2),D(2,0),E(0,2),F(1,0)$.

y
2 |  E---------C
  |  |       / |
1 |  |   B  /  |        B,F nằm BÊN TRONG -> sẽ bị loại
  |  | /      |
0 |  A----F---D
  +--+---+---+--- x
     0   1   2

Bước 1 — sắp xếp theo (x, y):

A(0,0)  E(0,2)  F(1,0)  B(1,1)  C(2,2)  D(2,0)

Bước 2 — dựng BAO DƯỚI (quét trái → phải, giữ rẽ phải / CW, tức cross <= 0 thì pop):

Bao dưới = A(0,0) → D(2,0) (đường đáy phẳng, đúng như hình).

Bước 3 — dựng BAO TRÊN (quét phải → trái: D, C, B, F, E, A):

Ghép lại (bỏ điểm đầu trùng), bao lồi cuối cùng theo chiều CCW:

A(0,0) -> D(2,0) -> C(2,2) -> E(0,2)

Đúng là hình chữ nhật ngoài cùng; $B$ và $F$ bị loại vì nằm bên trong.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x, y;
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    bool operator==(const Point& p) const {
        return x == p.x && y == p.y;
    }
};

// Tích chéo của OA và OB. >0: rẽ trái (CCW), <0: rẽ phải, =0: thẳng hàng.
long long cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Trả về bao lồi theo chiều ngược kim đồng hồ (CCW), không lặp lại điểm đầu.
vector<Point> convex_hull(vector<Point> pts) {
    int n = pts.size();
    if (n < 3) {              // 0,1,2 điểm: bao lồi suy biến, trả về luôn
        sort(pts.begin(), pts.end());
        pts.erase(unique(pts.begin(), pts.end()), pts.end());
        return pts;
    }
    sort(pts.begin(), pts.end());                 // sắp theo (x, y)
    pts.erase(unique(pts.begin(), pts.end()), pts.end());  // bỏ điểm trùng
    n = pts.size();
    if (n < 3) return pts;

    vector<Point> hull(2 * n);
    int k = 0;  // số điểm hiện có trong hull

    // BAO DƯỚI: quét trái -> phải, giữ rẽ trái nghiêm ngặt.
    // cross <= 0 nghĩa là rẽ phải hoặc thẳng hàng -> pop để loại điểm lõm.
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }

    // BAO TRÊN: quét phải -> trái. Bắt đầu từ phần tử áp chót (i = n-2).
    // 't' chốt số điểm tối thiểu để không phá bao dưới đã dựng.
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }

    hull.resize(k - 1);  // điểm cuối trùng điểm đầu -> bỏ
    return hull;
}

Nếu muốn giữ cả điểm thẳng hàng nằm trên cạnh bao (một số bài yêu cầu), đổi điều kiện pop từ <= 0 thành < 0 (chỉ pop khi rẽ phải thực sự).

Diện tích bao lồi bằng công thức diện tích Gauss (shoelace):

double hull_area(const vector<Point>& h) {
    long long area2 = 0;
    int n = h.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area2 += h[i].x * h[j].y - h[j].x * h[i].y; // tổng các tích chéo
    }
    return llabs(area2) / 2.0;
}

Rotating Calipers — đường kính bao lồi $O(N)$

Sau khi đã có bao lồi, tìm cặp điểm xa nhất (đường kính) bằng kỹ thuật "kẹp xoay" (rotating calipers): với mỗi cạnh, điểm xa nhất khỏi cạnh đó quét đơn điệu quanh đa giác, không lùi lại.

long long dist2(const Point& a, const Point& b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

// Diện tích (gấp đôi) tam giác qua tích chéo 2 vector cạnh.
long long area2(const Point& a, const Point& b, const Point& c) {
    return llabs(cross(a, b, c));
}

long long diameter2(const vector<Point>& h) {
    int n = h.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(h[0], h[1]);

    long long ans = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n;
        // Đẩy j tiến chừng nào điểm kế tiếp còn xa cạnh (i, ni) hơn.
        while (area2(h[i], h[ni], h[(j + 1) % n]) > area2(h[i], h[ni], h[j]))
            j = (j + 1) % n;
        ans = max({ans, dist2(h[i], h[j]), dist2(h[ni], h[j])});
    }
    return ans;
}

Độ phức tạp

• Thời gian dựng bao: $O(N\log N)$. Khâu nặng nhất là sắp xếp $O(N\log N)$. Phần quét hai lượt là $O(N)$: mỗi điểm được đẩy vào hull đúng một lần và bị pop nhiều nhất một lần, nên tổng số thao tác stack $\le 2N$ — vòng while tuy lồng nhưng tính gộp (amortized) vẫn tuyến tính.
• Rotating calipers: $O(N)$ trên bao đã dựng, vì con trỏ j chỉ tiến, đi tối đa $2N$ bước cho toàn bộ vòng.
• Bộ nhớ: $O(N)$ — lưu mảng điểm và mảng hull (cấp phát $2N$ vì lúc cao điểm bao trên + bao dưới chưa gộp).

⚠️ Lỗi thường gặp

• Tràn số (overflow) khi tính tích chéo. Với $|x|,|y|$ tới ${10}^9$, tích $(A_x-O_x)(B_y-O_y)$ có thể tới $~4·{10}^{18}$ — vượt int rất xa, sát trần long long. Luôn để tọa độ và tích chéo ở kiểu long long. Tính bằng int sẽ cho dấu sai và bao lồi méo mó.
• Nhầm dấu điều kiện pop (<= 0 vs < 0). <= 0 loại luôn điểm thẳng hàng (bao tối giản, chỉ giữ đỉnh thật). < 0 giữ điểm trên cạnh. Chọn sai sẽ sai số đỉnh khi bài có nhiều điểm collinear (ví dụ bài yêu cầu đếm điểm trên biên).
• Không khử điểm trùng trước khi dựng. Hai điểm trùng tọa độ làm cross ra 0 bất thường và có thể gây vòng lặp/đẩy-pop sai. Luôn sort rồi unique.
• Quên các trường hợp biên: $N=0,1,2$, hoặc tất cả điểm thẳng hàng (bao lồi suy biến thành đoạn thẳng). Code phải trả kết quả hợp lệ thay vì truy cập hull[k-2] khi k < 2. Điều kiện k >= 2 (và k >= t cho bao trên) chính là để chặn lỗi này.
• Lặp lại điểm đầu/cuối. Monotone chain để điểm cuối trùng điểm đầu; phải resize(k-1) để bỏ, nếu không diện tích/chu vi bị tính dư một cạnh độ dài 0 (thường vô hại) nhưng đếm số đỉnh sẽ sai.
• Dùng số thực không cần thiết. Mọi so sánh hướng đều làm được bằng số nguyên qua cross. Đưa về double sớm gây sai số dấu phẩy động khiến điểm gần thẳng hàng bị phân loại sai.

Biến thể / Mở rộng

• Graham scan: thuật toán cổ điển khác, sắp xếp các điểm theo góc cực quanh điểm thấp nhất rồi quét một vòng. Cùng độ phức tạp $O(N\log N)$ nhưng Monotone Chain dễ cài đúng hơn (sắp theo tọa độ thay vì theo góc, tránh xử lý góc bằng số thực).
• Kiểm tra điểm trong đa giác lồi $O(\log N)$: sau khi có bao, dùng tìm kiếm nhị phân theo góc để hỏi nhanh một điểm có nằm trong hay không (chính là cốt lõi của bài cowcurling bên dưới).
• Convex Hull Trick (CHT): khi tối ưu $dp[i]={min}_j(a_j·x_i+b_j)$, tập đường thẳng cần thiết tạo thành một bao lồi (dưới); duy trì bao này cho phép truy vấn $O(\log N)$ hoặc $O(1)$.
• Dynamic convex hull: thêm/xóa điểm trực tuyến và truy vấn (xem bài fencinggo).

Bài tập luyện

• Cow Curling (cowcurling) — (Kỳ cựu) Dựng bao lồi cho hai đội điểm rồi đếm điểm của đội kia nằm trong/biên — luyện dựng hull và kiểm tra điểm trong đa giác lồi, đúng bài toán cốt lõi.
• Những Ngọn Núi (mountain) — (Kỳ cựu) Hai núi nhìn thấy nhau khi không có núi nào nằm trên đoạn nối đỉnh — chính là điều kiện "rẽ trái" bằng tích chéo trên dãy độ cao (upper hull một chiều), luyện áp dụng tư duy bao lồi vào dãy số.
• Rào Đàn Bò Gold (fencinggo) — (Kỳ cựu) Thêm điểm động và kiểm tra mọi con bò nằm cùng một phía của đường thẳng — bài bao lồi động (dynamic convex hull), nâng cao và đòi hỏi duy trì hull khi tập điểm thay đổi.