Convex Hull ด้วย Monotone Chain Algorithm (Andrew's Algorithm) ใน C++

ภาพรวม

Monotone Chain Algorithm (Andrew's Algorithm) หา Convex Hull ใน O(n log n) โดย:

1. เรียงจุดตาม X (แล้ว Y)
2. สร้าง Lower Hull (ซ้าย→ขวา)
3. สร้าง Upper Hull (ขวา→ซ้าย)
4. รวมกัน (ตัดจุดซ้ำ頭/ท้าย)

หลักการ Cross Product

สำหรับ 3 จุด O, A, B:

cross(O, A, B) = (A.x - O.x)*(B.y - O.y) - (A.y - O.y)*(B.x - O.x)
> 0: Counter-clockwise (Left Turn)
< 0: Clockwise (Right Turn)
= 0: Collinear

โค้ดตัวอย่าง (C++)

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

using ll = long long;

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

ll 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);
}

vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n <= 3) return points;

    sort(points.begin(), points.end());

    vector<Point> hull(2 * n);
    int k = 0;

    // Lower Hull
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], points[i]) <= 0)
            k--;
        hull[k++] = points[i];
    }

    // Upper Hull
    for (int i = n-1, t = k+1; i > 0; --i) {
        while (k >= t && cross(hull[k-2], hull[k-1], points[i-1]) <= 0)
            k--;
        hull[k++] = points[i-1];
    }

    hull.resize(k - 1);  // Remove duplicate last point
    return hull;
}

int main() {
    vector<Point> points = {{0,3}, {2,2}, {1,1}, {2,1}, {3,0}, {0,0}, {3,3}};
    auto hull = convexHull(points);

    for (const auto& p : hull)
        cout << "(" << p.x << ", " << p.y << ")" << endl;

    return 0;
}

ผลลัพธ์

(0, 0)
(3, 0)
(3, 3)
(0, 3)

Complexity Analysis

• Time: O(n log n) (Dominated by Sorting)
• Space: O(n)
• Output-Sensitive: จริงๆ เป็น O(n log h) แต่ Sorting ทำให้เป็น O(n log n)

คำอธิบายเพิ่มเติม

• Simpler และเร็วกว่า Graham Scan และ Divide & Conquer ในทางปฏิบัติ
• ไม่ต้องคำนวณ Polar Angle (ไม่ใช้ Trigonometry)
• จัดการ Collinear Points: โค้ดนี้ ตัด Collinear Points ระหว่างทางออก (ใช้ <= 0), ถ้าต้องการเก็บไว้ เปลี่ยนเป็น < 0
• ทำงานได้กับ Integer Coordinates อย่างแม่นยำ (ไม่มี Floating Point Error)
• Standard Algorithm สำหรับ Convex Hull ใน CP (Competitive Programming)

เปรียบเทียบ Convex Hull Algorithms