vi
new
+4
Avatar
Viblo Algorithm @algorithm
10.5K 782 122
Đã đăng vào thg 4 16, 9:00 SA 17 phút đọc
2.0K

Các thuật toán tìm Bao lồi (Convex hull)

Để 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:

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,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.

image.png

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 nn điểm trên mặt phẳng tọa độ Oxy,Oxy, điểm thứ ii có tọa độ là xi,yix_i, y_i. Hãy tìm ra các điểm tạo thành bao lồi của tập nn điểm trên?

Input:

  • Dòng đầu tiên chứa số nguyên dương nn.
  • Trên nn dòng tiếp theo, mỗi dòng chứa hai số nguyên xi,yix_i, y_i.

Ràng buộc:

  • 1≤n≤1051 \le n \le 10^5.
  • ∣xi∣,∣yi∣≤109;∀i:1≤i≤n|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à OO. Bước này sẽ có độ phức tạp thời gian O(n)O(n).

Ta tạo một hệ trục tọa độ với gốc là điểm P0P_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 P0I→\overrightarrow{P_0I} - với II 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 P0P_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 P0P_0. Bước này sẽ tốn độ phức tạp O(n×log⁡n)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(P0,A,B)CW(P_0, A, B) hoặc CCW(P0,A,B)CCW(P_0, A, B) - tức là hướng đi từ P0→A→BP_0 \to A \to B có phải theo chiều kim đồng hồ hay không. Nếu như CW(P0,A,B)<0CW(P_0, A, B) < 0 thì hướng đi là xuôi chiều kim đồng hồ, nếu CW(P0,A,B)=0CW(P_0, A, B) = 0 thì ba điểm sẽ thẳng hàng, còn nếu CW(P0,A,B)>0CW(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 CCWCCW). 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(P0,A,B)CW(P_0, A, B). Bản chất của hàm này là xét tích có hướng P0A→×AB→\overrightarrow{P_0A} \times \overrightarrow{AB}. Nếu như tích này âm, tức là điểm BB nằm dưới điểm AA trên mặt phẳng tọa độ, cũng đồng nghĩa với góc cầu hình của AA sẽ lớn hơn góc cầu hình của B,B, và điểm AA phải nằm trước BB 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 pi,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 pip_i tạo một hướng đi theo chiều kim đồng hồ, thì tạm thời ghi nhận pip_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 CWCW.
  • 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 11 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 P0P_0 nhất và thẳng hàng với P0P_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 CCWCCW sẽ được sử dụng thay vì hàm CW,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→B→CA \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 CWCW trong cả hai trường hợp: Bao lồi không chứa các điểm thẳng hàng (include_collinear = false)(\text{include\_collinear = false}) và Bao lồi có chứa các điểm thẳng hàng include_collinear = true)\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×log⁡n)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×log⁡n)O(n \times \log n).
  • Độ phức tạp không gian: O(n)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).

image.png

Đầ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à firstfirst và lastlast.

Nếu như kẻ một đường thẳng nối firstfirst và last,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 upup và downdown 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 firstfirst.

Xét điểm pip_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→lastfirst \to last: Nếu nó thuộc nửa trên thì hướng đi first→pi→lastfirst \to p_i \to last phải theo chiều kim đồng hồ, công thức CWCW sẽ hữu ích ở đây. Còn nếu nó thuộc nửa dưới thì hướng đi first→pi→lastfirst \to p_i \to last phải ngược chiều kim đồng hồ, ta sử dụng công thức CCWCCW để kiểm tra. Trường hợp đặc biệt là điểm pip_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 pip_i thuộc nửa trên: Gọi hai điểm cuối cùng thuộc bao trên là pmp_m và pm−1,p_{m - 1}, thì hướng đi pm−1→pm→pip_{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 pip_i vào tập bao trên upup.
  • Nếu pip_i thuộc nửa dưới: Gọi hai điểm cuối cùng thuộc bao dưới là pmp_m và pm−1,p_{m - 1}, thì hướng đi pm−1→pm→pip_{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 pip_i vào tập bao dưới downdown.

Việc kiểm tra hướng thông qua hàm CWCW và CCWCCW 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ố include_collinear\text{include\_collinear} thể hiện cho điều này và nó được đưa vào các hàm CWCW cũng như CCWCCW để 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 22 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×log⁡n)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)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 nn ô nhớ.

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

1. Area Convex

Đề bài

Cho một dãy số nguyên aa gồm nn phần tử. Tập điểm SS trên hệ trục tọa độ OxyOxy sẽ được xây dựng từ dãy aa. Cụ thể hơn, nó bao gồm các điểm có tọa độ (ai,aj);∀i,j:1≤i<j≤n(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 SS là C,Area(C)C, Area(C) là diện tích của CC. Hãy tính 2×Area(C)?2 \times Area(C)?

Input:

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

Ràng buộc:

  • 3≤n≤1053 \le n \le 10^5.
  • 1≤ai≤108;∀i:1≤i≤n1 \le a_i \le 10^8; \forall i: 1 \le i \le n.

Output:

  • In ra 2×Area(C),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 DCFEADCFEA chính là bao lồi của tập điểm và 2×Area(C)=2×6.5=132 \times Area(C) = 2 \times 6.5 = 13.

Ý tưởng

Ta nhận thấy rằng, với mỗi aia_i, khi ta dựng các điểm có dạng (ai,aj) (i<j≤n);(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 22 đỉnh đầu và cuối, có nghĩa với mỗi aia_i chỉ cần dựng ra 22 đỉnh (ai,max(aj);∀j∈[i+1,n])\big(a_i,\text{max}(a_j); \forall j \in [i + 1, n]\big) và (ai,min(aj);∀j∈[i+1,n])\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 OxyOxy.

Độ phức tạp: O(n×log⁡)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 nn điểm trên mặt phẳng tọa độ OxyOxy.

Yêu cầu: Hãy tìm 33 đ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 nn là số lượng điểm.
  • Trên nn dòng tiếp theo, mỗi dòng chứa 33 số nguyên xi,yix_i,y_i - với xi,yix_i,y_i là tọa độ của điểm thứ ii.

Ràng buộc:

  • 3≤n≤30003 \le n \le 3000.
  • Tọa độ của các điểm đều là số nguyên trong phạm vi [−106,106][-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ừ 33 đ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 33 điểm rồi tính diện tích tam giác.

Subtask 2

Ta có nhận xét rằng, 33 đ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 22 đỉnh trên đa giác như sau:

Imgur

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

Độ phức tạp: O(n2)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

Competitive Programming maths Viblo Algorithm

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí