Để hiểu được nội dung trong bài viết này, các bạn cần nắm vững các kiến thức về Hình học tính toán cơ bản. Các bạn có thể xem lại hai bài viết này tại các link dưới đây:

• Những vấn đề cơ bản về Vector.
• Sự giao nhau của các đường thẳng và Tính toán diện tích.

I. Định nghĩa Bao lồi

Bao lồi là một vấn đề rất thường xuyên xuất hiện trong các bài tập hình học tính toán của lập trình thi đấu.

Xét một tập điểm trên mặt phẳng tọa độ $Oxy,$ bao lồi của tập điểm là tập lồi nhỏ nhất (theo diện tích, thể tích,...) mà chứa tất cả các điểm đó. Nói cách khác, bao lồi của một tập điểm là đa giác nhỏ nhất chứa tất cả các điểm đó.

Một cách trực quan, nếu coi mỗi điểm như một chiếc đinh đóng trên tấm gỗ, bao lồi của tập điểm đó sẽ có viền ngoài là một sợi dây sau khi bị kéo căng vào những chiếc đinh ở các phía.

Trong bài viết này, chúng ta sẽ cùng nghiên cứu một số thuật toán phổ biến để tìm ra bao lồi của một tập điểm. Bài toán tìm bao lồi có thể phát biểu ngắn gọn như sau:

Cho $n$ điểm trên mặt phẳng tọa độ $Oxy,$ điểm thứ $i$ có tọa độ là $x_i, y_i$. Hãy tìm ra các điểm tạo thành bao lồi của tập $n$ điểm trên?

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 hai số nguyên $x_i, y_i$.

Ràng buộc:

• $1 \le n \le 10^5$.
• $|x_i|, |y_i| \le 10^9; \forall i: 1 \le i \le n$

Output:

• In ra các điểm thuộc bao lồi của tập điểm đã cho theo chiều kim đồng hồ, mỗi điểm trên một dòng gồm hoành độ và tung độ.

Sample Input:

6
2 1
1 3
2 3
2 4
4 1
4 3

Sample Output:

1 3
2 4
4 3
4 1
2 1

II. Các thuật toán tìm Bao lồi thông dụng

1. Thuật toán Graham

Ý tưởng

Thuật toán Graham (Graham scan algorithm) được nhà toán học người Mỹ Ronald Graham tìm ra vào năm 1972. Thuật toán này sẽ tìm ra tất cả các đỉnh của bao lồi theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, tùy vào cách cài đặt.

Thuật toán xuất phát từ một đỉnh chắc chắn thuộc bao lồi - thường sẽ là điểm có tung độ nhỏ nhất, nếu có nhiều điểm như vậy thì ta chọn điểm ở bên trái nhất. Coi điểm này là $O$. Bước này sẽ có độ phức tạp thời gian $O(n)$.

Ta tạo một hệ trục tọa độ với gốc là điểm $P_0$ vừa chọn, rồi sắp xếp các điểm còn lại theo chiều giảm dần của góc tạo bởi chiều dương trục hoành với vector $\overrightarrow{P_0I}$ - với $I$ là một trong các điểm còn lại - góc này còn được gọi là góc cầu hình (polar angle xung quanh điểm $P_0$. Nếu như góc này giữa hai hoặc nhiều cặp điểm giống nhau, thì ta sẽ sắp xếp tăng dần các điểm theo khoảng cách tới điểm $P_0$. Bước này sẽ tốn độ phức tạp $O(n \times \log n)$.

Một kiến thức quan trọng sẽ sử dụng lại ở đây là hàm $CW(P_0, A, B)$ hoặc $CCW(P_0, A, B)$ - tức là hướng đi từ $P_0 \to A \to B$ có phải theo chiều kim đồng hồ hay không. Nếu như $CW(P_0, A, B) < 0$ thì hướng đi là xuôi chiều kim đồng hồ, nếu $CW(P_0, A, B) = 0$ thì ba điểm sẽ thẳng hàng, còn nếu $CW(P_0, A, B) > 0$ thì hướng đi sẽ là ngược chiều kim đồng hồ (xử lý ngược lại đối với hàm $CCW$). Lúc này ta cần xử lý thêm tùy vào trường hợp bài toán yêu cầu có lấy các điểm nằm thẳng hàng trên bao lồi hay không.

Để sắp xếp lại các điểm theo góc cầu hình giảm dần, ta sử dụng tới công thức $CW(P_0, A, B)$. Bản chất của hàm này là xét tích có hướng $\overrightarrow{P_0A} \times \overrightarrow{AB}$. Nếu như tích này âm, tức là điểm $B$ nằm dưới điểm $A$ trên mặt phẳng tọa độ, cũng đồng nghĩa với góc cầu hình của $A$ sẽ lớn hơn góc cầu hình của $B,$ và điểm $A$ phải nằm trước $B$ trong tập điểm. Còn nếu ba điểm thẳng hàng thì ta đơn giản sử dụng công thức khoảng cách Euclid để sắp xếp chúng lại.

Bước tiếp theo, ta xét từng điểm trong tập điểm và dùng một vector để lưu trữ các điểm thuộc bao lồi. Giả sử đang xét tới điểm $p_i,$ thì có hai trường hợp sẽ xảy ra:

• Nếu như hai điểm trước đó thuộc bao lồi và điểm $p_i$ tạo một hướng đi theo chiều kim đồng hồ, thì tạm thời ghi nhận $p_i$ vào bao lồi. Việc kiểm tra này một lần nữa vận dụng tới công thức $CW$.
• Ngược lại, cần loại bỏ các điểm trước đó đã ghi nhận vào bao lồi cho tới khi trường hợp $1$ thỏa mãn, bởi vì nếu như hướng đi không theo chiều kim đồng hồ thì nó sẽ tạo ra một phần lõm trên biên của đa giác.

Nếu như bài toán yêu cầu lấy cả những điểm thẳng hàng trên bao lồi (tức là thuộc cạnh của bao lồi), thì sau khi sắp xếp lại các điểm, ta cần thực hiện thêm một bước phụ: Chọn ra các điểm ở xa $P_0$ nhất và thẳng hàng với $P_0$ - những điểm này sẽ nằm ở cuối danh sách. Sau đó, đảo ngược tất cả những điểm này, thì thuật toán sẽ ghi nhận được tất cả các điểm thẳng hàng nhau trên bao lồi.

Lưu ý: Nếu như muốn đưa ra các điểm trên bao lồi theo chiều ngược kim đồng hồ, thì ta cần sắp xếp lại các điểm tăng dần theo góc cầu hình. Khi đó hàm $CCW$ sẽ được sử dụng thay vì hàm $CW,$ các bạn chỉ cần chỉnh sửa một chút từ cài đặt bên dưới.

Cài đặt

Trong cài đặt dưới đây, việc xác định hướng đi của ba điểm $A \to B \to C$ là thuận chiều kim đồng hồ hay ngược chiều kim đồng hồ được cài đặt ở hàm int orientation(a, b, c). Hàm này sẽ được sử dụng lại ở hàm bool cw(a, b, c, include_collinear) để xét được công thức $CW$ trong cả hai trường hợp: Bao lồi không chứa các điểm thẳng hàng $(\text{include\_collinear = false})$ và Bao lồi có chứa các điểm thẳng hàng $\text{include\_collinear = true})$.

#include <bits/stdc++.h> using namespace std; struct Point
{ int x, y; Point() {} Point(int _x, int _y) : x(_x), y(_y) {} int dist(const Point& other) { return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y); }
}; struct Vector
{ int x, y; Vector() {} Vector(int _x, int _y) : x(_x), y(_y) {} double cross_product(const Vector& other) { return x * other.y - y * other.x; }
}; Vector operator - (const Point& a, const Point& b)
{ return Vector(a.x - b.x, a.y - b.y);
} // Xác định hướng đi từ A -> B -> C.
int orientation(const Point& a, const Point& b, const Point& c)
{ Vector x = b - a; Vector y = c - b; int orient = x.cross_product(y); if (orient < 0) // Cùng chiều kim đồng hồ. return -1; else if (orient == 0) // Thẳng hàng. return 0; return 1; // Ngược chiều kim đồng hồ.
} bool collinear(const Point& a, const Point& b, const Point& c)
{ return orientation(a, b, c) == 0;
} bool cw(const Point& a, const Point& b, const Point& c, bool include_collinear)
{ int orient = orientation(a, b, c); return (orient < 0) || (orient == 0 && include_collinear);
} vector < Point > convex_hull(const int& n, vector < Point >& p, bool include_collinear = false)
{ Point p0 = *min_element(p.begin() + 1, p.end(), [](Point a, Point b) { return make_pair(a.y, a.x) < make_pair(b.y, b.x); }); sort(p.begin() + 1, p.end(), [&p0](const Point& a, const Point& b) { int orient = orientation(p0, a, b); // Góc cầu hình của A = Góc cầu hình của B thì sắp xếp theo khoảng cách tới P0. if (orient == 0) return p0.dist(a) < p0.dist(b); // Thứ tự mong muốn là Góc cầu hình của A < Góc cầu hình của B. // Nếu P0 -> A -> B theo chiều kim đồng hồ tức là B ở dưới A trên mặt phẳng, thì // góc cầu hình của A sẽ lớn hơn góc cầu hình của B. return orient < 0; }); // Trường hợp bao lồi yêu cầu phải chứa các điểm thẳng hàng. if (include_collinear) { int i = n; while (i >= 1 && collinear(p0, p[i], p.back())) --i; reverse(p.begin() + i + 1, p.end()); } vector < Point > hull; for (int i = 1; i < (int) p.size(); ++i) { while (hull.size() > 1 && !cw(hull[hull.size() - 2], hull.back(), p[i], include_collinear)) hull.pop_back(); hull.push_back(p[i]); } return hull;
} signed main()
{ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector < Point > p(n + 1); for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y; vector < Point > hull = convex_hull(n, p); for (auto p: hull) cout << p.x << ' ' << p.y << endl; return 0;
}

Đánh giá

• Độ phức tạp thời gian: $O(n \times \log n)$. Bước lâu nhất trong thuật toán là bước sắp xếp lại các điểm, nên độ phức tạp tổng quát là $O(n \times \log n)$.
• Độ phức tạp không gian: $O(n)$. Do chỉ có một vector được sử dụng để lưu trữ bao lồi, không có thêm không gian phụ nào được sử dụng.

2. Thuật toán Motonone Chain

Ý tưởng

Thuật toán Andrew's Motonone Chain - hay còn gọi là thuật toán Chuỗi đơn điệu, được sáng lập bởi A.M. Andrew vào năm 1979 - là một trong những thuật toán tìm bao lồi vô cùng hiệu quả, dễ cài đặt, và thường được khuyên dùng trong mọi bài toán liên quan tới bao lồi.

Thuật toán này được xây dựng dựa trên ý tưởng xây dựng hai chuỗi đơn điệu của bao lồi: Bao trên (chuỗi trên) và Bao dưới (chuỗi dưới).

Đầu tiên, ta sẽ chọn ra hai điểm xa nhất về bên trái và bên phải trong tập điểm, đó sẽ là hai điểm luôn luôn thuộc bao lồi. Để làm như vậy, ta sắp xếp lại các điểm tăng dần theo hoành độ, nếu hoành độ bằng nhau thì sắp xếp tăng dần theo tung độ. Sau bước này, điểm trái nhất sẽ nằm ở đầu danh sách, và điểm phải nhất sẽ nằm ở cuối danh sách. Ta gọi hai điểm đó là $first$ và $last$.

Nếu như kẻ một đường thẳng nối $first$ và $last,$ thì tập điểm sẽ bị chia làm hai nửa: Một nửa nằm bên trên đường thẳng sẽ chứa các điểm thuộc bao trên của bao lồi, một nửa nằm bên dưới đường thẳng sẽ chứa các điểm thuộc bao dưới của bao lồi. Còn những điểm nằm trên đường thẳng này có thể thuộc một trong hai bao trên hoặc bao dưới.

Ta sẽ xây dựng hai tập $up$ và $down$ chứa bao trên và bao dưới. Ban đầu, cả hai tập này đều chứa duy nhất điểm $first$.

Xét điểm $p_i$ trong tập điểm (không tính hai điểm đầu và cuối đã ghi nhận sẵn), ta cần xử lý như sau:

• Kiểm tra xem điểm này thuộc nửa trên hay nửa dưới của đoạn nối $first \to last$: Nếu nó thuộc nửa trên thì hướng đi $first \to p_i \to last$ phải theo chiều kim đồng hồ, công thức $CW$ sẽ hữu ích ở đây. Còn nếu nó thuộc nửa dưới thì hướng đi $first \to p_i \to last$ phải ngược chiều kim đồng hồ, ta sử dụng công thức $CCW$ để kiểm tra. Trường hợp đặc biệt là điểm $p_i$ chính là điểm cuối, thì ta coi như nó thuộc cả hai nửa (không cần kiểm tra hướng đi).
• Nếu $p_i$ thuộc nửa trên: Gọi hai điểm cuối cùng thuộc bao trên là $p_m$ và $p_{m - 1},$ thì hướng đi $p_{m - 1} \to p_m \to p_i$ phải theo chiều kim đồng hồ, ngược lại ta cần loại bỏ các điểm ở cuối bao lồi đã dựng tới khi điều kiện trên thỏa mãn thì ghi nhận $p_i$ vào tập bao trên $up$.
• Nếu $p_i$ thuộc nửa dưới: Gọi hai điểm cuối cùng thuộc bao dưới là $p_m$ và $p_{m - 1},$ thì hướng đi $p_{m - 1} \to p_m \to p_i$ phải ngược chiều kim đồng hồ, ngược lại ta cần loại bỏ các điểm ở cuối bao lồi đã dựng tới khi điều kiện trên thỏa mãn thì ghi nhận $p_i$ vào tập bao dưới $down$.

Việc kiểm tra hướng thông qua hàm $CW$ và $CCW$ vẫn sẽ cần lưu ý tới điều kiện của bài toán có yêu cầu tính các điểm thẳng hàng trên bao lồi hay không. Trong cài đặt mẫu, tham số $\text{include\_collinear}$ thể hiện cho điều này và nó được đưa vào các hàm $CW$ cũng như $CCW$ để tiện xử lý tổng quát cho cả hai trường hợp bài toán.

Cuối cùng, ta chỉ cần gộp hai bao trên và dưới lại thành bao lồi cuối cùng. Tuy nhiên cần lưu ý không lấy điểm đầu và điểm cuối $2$ lần, vì cả hai điểm này đều xuất hiện trong cả hai bao trên và bao dưới. Bao lồi cuối cùng sẽ gồm các điểm đi theo chiều kim đồng hồ.

Cài đặt

#include <bits/stdc++.h>
#define int long long using namespace std; struct Point
{ int x, y; Point() {} Point(int _x, int _y) : x(_x), y(_y) {} bool operator < (const Point& other) { return (x < other.x) || (x == other.x && y < other.y); }
}; struct Vector
{ int x, y; Vector() {} Vector(int _x, int _y) : x(_x), y(_y) {} double cross_product(const Vector& other) { return x * other.y - y * other.x; }
}; Vector operator - (const Point& a, const Point& b)
{ return Vector(a.x - b.x, a.y - b.y);
} // Xác định hướng đi A -> B -> C.
int orientation(const Point& a, const Point& b, const Point& c)
{ Vector x = b - a; Vector y = c - b; int orient = x.cross_product(y); if (orient < 0) // Cùng chiều kim đồng hồ. return -1; else if (orient == 0) // Thẳng hàng. return 0; return 1; // Ngược chiều kim đồng hồ.
} bool ccw(const Point& a, const Point& b, const Point& c, bool include_collinear = false)
{ int orient = orientation(a, b, c); return (orient > 0) || (orient == 0 && include_collinear);
} bool cw(const Point& a, const Point& b, const Point& c, bool include_collinear = false)
{ int orient = orientation(a, b, c); return (orient < 0) || (orient == 0 && include_collinear);
} vector < Point > convex_hull(int n, vector < Point >& p, bool include_collinear = false)
{ sort(p.begin() + 1, p.end()); Point first = p[1], last = p[n]; vector < Point > up(1, first); vector < Point > down(1, first); for (int i = 2; i <= n; ++i) { if (i == n || cw(first, p[i], last, include_collinear)) { while (up.size() >= 2 && !cw(up[up.size() - 2], up.back(), p[i], include_collinear)) up.pop_back(); up.push_back(p[i]); } if (i == n || ccw(first, p[i], last, include_collinear)) { while (down.size() >= 2 && !ccw(down[down.size() - 2], down.back(), p[i], include_collinear)) down.pop_back(); down.push_back(p[i]); } } vector < Point > hull; for (int i = 0; i < up.size(); ++i) hull.push_back(up[i]); for (int i = down.size() - 2; i >= 1; --i) hull.push_back(down[i]); return hull;
} signed main()
{ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector < Point > p(n + 1); for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y; vector < Point > hull = convex_hull(n, p); for (auto p: hull) cout << p.x << ' ' << p.y << endl; return 0;
}

Đánh giá

• Độ phức tạp thời gian: $O(n \times \log n)$. Thao tác sắp xếp là thao tác tốn nhiều thời gian nhất.
• Độ phức tạp không gian: $O(n)$. Các mảng và vector sử dụng đều là một chiều nên tối đa chỉ cần $n$ ô nhớ.

III. Bài tập minh họa

1. Area Convex

Đề bài

Cho một dãy số nguyên $a$ gồm $n$ phần tử. Tập điểm $S$ trên hệ trục tọa độ $Oxy$ sẽ được xây dựng từ dãy $a$. Cụ thể hơn, nó bao gồm các điểm có tọa độ $(a_i,a_j); \forall i, j: 1 \le i < j \le n$.

Yêu cầu: Gọi bao lồi của tập điểm $S$ là $C, Area(C)$ là diện tích của $C$. Hãy tính $2 \times Area(C)?$

Input:

• Dòng đầu gồm số nguyên dương $n$ là độ dài dãy $a$.
• Dòng thứ hai gồm $n$ số nguyên $a_1,a_2,...,a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $3 \le n \le 10^5$.
• $1 \le a_i \le 10^8; \forall i: 1 \le i \le n$.

Output:

• In ra $2 \times Area(C),$ có thể chắc chắn rằng đây là một số nguyên.

Sample Input:

4
2 4 1 3

Sample Output:

13

Giải thích:

Đa giác $DCFEA$ chính là bao lồi của tập điểm và $2 \times Area(C) = 2 \times 6.5 = 13$.

Ý tưởng

Ta nhận thấy rằng, với mỗi $a_i$, khi ta dựng các điểm có dạng $(a_i,a_j) \ (i < j \le n);$ nó sẽ tạo ra một đường thẳng, vậy nên những điểm nằm ở giữa là không cần thiết vì chắc chắn nó sẽ không thuộc bao lồi, vậy ta chỉ cần quan tâm $2$ đỉnh đầu và cuối, có nghĩa với mỗi $a_i$ chỉ cần dựng ra $2$ đỉnh $\big(a_i,\text{max}(a_j); \forall j \in [i + 1, n]\big)$ và $\big(a_i,\text{min}(a_j); \forall j \in [i + 1, n]\big)$.

Việc tính diện tích của bao lồi có thể sử dụng công thức tính diện tích đa giác trên mặt phẳng $Oxy$.

Độ phức tạp: $O(n \times \log)$.

Cài đặt

#include <bits/stdc++.h>
#define int long long using namespace std; struct Point
{ int x, y; Point() {} Point(int _x, int _y) : x(_x), y(_y) {} bool operator < (const Point& other) { return (x < other.x) || (x == other.x && y < other.y); }
}; struct Vector
{ int x, y; Vector() {} Vector(int _x, int _y) : x(_x), y(_y) {} double cross_product(const Vector& other) { return x * other.y - y * other.x; }
}; Vector operator - (const Point& a, const Point& b)
{ return Vector(a.x - b.x, a.y - b.y);
} // Xác định hướng đi A -> B -> C.
int orientation(const Point& a, const Point& b, const Point& c)
{ Vector x = b - a; Vector y = c - b; int orient = x.cross_product(y); if (orient < 0) // Cùng chiều kim đồng hồ. return -1; else if (orient == 0) // Thẳng hàng. return 0; return 1; // Ngược chiều kim đồng hồ.
} bool ccw(const Point& a, const Point& b, const Point& c, bool include_collinear = false)
{ int orient = orientation(a, b, c); return (orient > 0) || (orient == 0 && include_collinear);
} bool cw(const Point& a, const Point& b, const Point& c, bool include_collinear = false)
{ int orient = orientation(a, b, c); return (orient < 0) || (orient == 0 && include_collinear);
} vector < Point > convex_hull(int n, vector < Point >& a, bool include_collinear = false)
{ sort(a.begin(), a.end()); Point first = a[0], last = a.back(); vector < Point > up(1, first); vector < Point > down(1, first); for (int i = 1; i < n; ++i) { if (i == n - 1 || cw(first, a[i], last, include_collinear)) { while (up.size() >= 2 && !cw(up[up.size() - 2], up.back(), a[i], include_collinear)) up.pop_back(); up.push_back(a[i]); } if (i == n - 1 || ccw(first, a[i], last, include_collinear)) { while (down.size() >= 2 && !ccw(down[down.size() - 2], down.back(), a[i], include_collinear)) down.pop_back(); down.push_back(a[i]); } } vector < Point > hull; for (int i = 0; i < up.size(); ++i) hull.push_back(up[i]); for (int i = down.size() - 2; i >= 1; --i) hull.push_back(down[i]); return hull;
} int area(vector < Point >& hull)
{ hull.push_back(hull[0]); int res = 0, n = hull.size(); for (int i = 0; i <= n - 2; ++i) res += (hull[i].x - hull[i + 1].x) * (hull[i].y + hull[i + 1].y); return abs(res);
} signed main()
{ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector < int > p(n + 1); for (int i = 1; i <= n; ++i) cin >> p[i]; int miny = p[n], maxy = p[n]; vector < Point > a; for (int i = n - 1; i >= 1; --i) { a.push_back({p[i], miny}); a.push_back({p[i], maxy}); miny = min(miny, p[i]); maxy = max(maxy, p[i]); } vector < Point > hull = convex_hull(a.size(), a); cout << area(hull); return 0;
}

2. Tam giác lớn nhất

Đề bài

Cho $n$ điểm trên mặt phẳng tọa độ $Oxy$.

Yêu cầu: Hãy tìm $3$ điểm sao cho chúng tạo thành một tam giác không suy biến và diện tích của nó là lớn nhất có thể?

Input:

• Dòng đầu gồm số nguyên dương $n$ là số lượng điểm.
• Trên $n$ dòng tiếp theo, mỗi dòng chứa $3$ số nguyên $x_i,y_i$ - với $x_i,y_i$ là tọa độ của điểm thứ $i$.

Ràng buộc:

• $3 \le n \le 3000$.
• Tọa độ của các điểm đều là số nguyên trong phạm vi $[-10^6,10^6]$.

Output:

• In ra số nguyên duy nhất là diện tích tam giác lớn nhất được tạo thành từ $3$ điểm trong các điểm đã cho. Kết quả lấy chính xác tới chữ số thập phân thứ nhất.

Sample Input:

5
3 6
2 7
1 8
4 9
1 4

Sample Output:

6.0

Ý tưởng

Subtask 1

Cố định $3$ điểm rồi tính diện tích tam giác.

Subtask 2

Ta có nhận xét rằng, $3$ điểm cần tìm chắc chắn sẽ nằm trên bao lồi. Như vậy, đầu tiên ta tối giản tập điểm về bao lồi của nó.

Ta sẽ sử dụng tính chất của một đa giác lồi để giải bài toán này, đó là, nếu ta cố định $2$ đỉnh trên đa giác như sau:

• Giả sử ta đang cố định hai đỉnh $A$ và $B,$ ta có thể nhận thấy rằng diện tích tam giác mà được cố định bởi $A$ và $B$ sẽ tăng dần từ $C,E,D$ rồi lại giảm xuống từ $F,G$.
• Như vậy, $D$ chính là đỉnh cho ra, kết quả tối ưu khi ta cố định $A$ và $B$.
• Tiếp đó, nếu ta chuyển từ cố định $A,B$ sang $A,H,$ ta nhận thấy tính chất này vẫn tiếp tục từ $D,$ tam giác cố định bởi $A,H$ sẽ tăng dần diện tích từ $C,E,D,F$ và giảm xuống ở $G,B$.
• Như vậy, ta có thể sử dụng thuật toán $2$ con trỏ để tìm đỉnh tốt nhất sau khi cố định $2$ đỉnh còn lại của tam giác. Sau đó chỉ việc lấy $\text{max}$ của chúng.

Độ phức tạp: $O(n^2)$.

Cài đặt

#include <bits/stdc++.h>
#define int long long using namespace std; struct Point
{ int x, y;
}; struct Vector { int x, y; int cross (const Vector& o) const { return x * o.y - y * o.x; }
}; const int maxn = 1e4 + 5;
int n, go[maxn];
vector < vector < int > > f;
vector < Point > a; Vector operator - (const Point& a, const Point& b)
{ return {a.x - b.x, a.y - b.y};
} int area(Point a, Point b, Point c) { Vector x = a - b; Vector y = c - b; int res = x.cross(y); if (res < 0) res = -res; return res;
} void solution() { for (int i = 0; i < n; ++i) go[i] = (i + 1) % n; f.resize(n + 5); for (int i = 0; i <= n + 2; ++i) f[i].resize(n + 5); int res = 0; for (int i = 0; i < n; ++i) { int best = go[i]; for (int j = (go[i] + 1) % n; j != i; j = go[j]) { while (best != j && area(a[i], a[best], a[j]) < area(a[i], a[go[best]], a[j])) best = go[best]; f[i][j] = area (a[i], a[best], a[j]); } } for (int i = 0; i < n; ++i) for (int j = (go[i] + 1) % n; j != i; j = go[j]) res = max(res, f[i][j]); int x = res / 2; cout << x; if (res % 2) cout << ".5"; else cout << ".0";
} signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; a.resize(n + 5); for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y; solution(); return 0;
}

IV. Tài liệu tham khảo

• https://cp-algorithms.com/geometry/convex-hull.html
• https://vnoi.info/wiki/translate/wcipeg/Convex-Hull.md
• https://www.geeksforgeeks.org/convex-hull-using-graham-scan/
• https://www.geeksforgeeks.org/convex-hull-monotone-chain-algorithm/