Thuật toán Gift Wrapping (bao bọc) tìm bao lồi 2D trong C++

Thuật toán Gift Wrapping (Jarvis March) tính bao lồi (convex hull) của tập điểm phẳng. Ý tưởng: bắt đầu từ điểm trái nhất, quay ngược chiều kim đồng hồ chọn điểm sao cho tất cả điểm khác nằm bên phải đường nối, lặp cho đến khi quay về điểm đầu.

Thuật toán

Bắt đầu
  convexHull(points[], n):
    nếu n < 3 trả về
    tìm điểm trái nhất (min x)
    p = điểm trái nhất
    lặp:
      q = (p+1)%n
      với mỗi i: nếu orient(p, i, q) == 2 (quay trái) thì q = i
      next[p] = q; p = q
    cho đến khi p == điểm trái nhất
    in các cạnh next[i] != -1
Kết thúc

Ví dụ minh họa

#include <iostream>
using namespace std;
#define INF 10000

struct Point { int x, y; };

int orient(Point a, Point b, Point c) {
    int v = (b.y - a.y)*(c.x - b.x) - (b.x - a.x)*(c.y - b.y);
    if (v == 0) return 0;       // thẳng hàng
    return (v > 0) ? 1 : 2;     // 1: kim đồng hồ, 2: ngược kim đồng hồ
}

void convexHull(Point pts[], int n) {
    if (n < 3) return;
    int next[n]; fill_n(next, n, -1);
    int l = 0;
    for (int i=1; i

Kết quả
Cac diem tren bao loi: (0,4) (4,1) (3,0) (1,1) (7,6)