graham.cpp (2)

Bài toán

Tìm bao lồi của một tập hợp các điểm (hai phần tử bất kì luôn phân biệt).

Độ phức tạp

tìm bao lồi : O(n logn)

bộ nhớ : O(n)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

#define X first

#define Y second

ii origin;

void operator-=(ii &A, ii B) {

    A.X -= B.X;

    A.Y -= B.Y;

}

bool ccw(ii O, ii A, ii B) {

    A -= O, B -= O;

    return A.X * B.Y > A.Y * B.X;

}

bool cmp(ii A, ii B) { return ccw(origin, A, B); }

int n;

ii a[12309];

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)

        scanf("%d%d", &a[i].X, &a[i].Y);

    sort(a + 1, a + n + 1);

    origin = a[1];

    sort(a + 2, a + n + 1, cmp);

    a[0] = a[n];

    a[n + 1] = a[1];

    int j = 1;

    for (int i = 1; i <= n + 1; i++) {  // a[1] and a[n+1] will be both added

        while (j > 2 && !ccw(a[j - 2], a[j - 1], a[i])) j--;

        a[j++] = a[i];

    }

    n = j - 2;

    for (int i = 1; i <= n; i++) printf("%d %d\n", a[i].X, a[i].Y);

}

Nhận xét

Code này đã được dùng để nộp cho một bài tập trên UVa.

Phần nhập input và xuất ra output đã được sửa đổi để bám sát đề bài.

Chương trình thực hiện lần lượt các thao tác sau

- Tìm một điểm chắc chắn thuộc về bao lồi làm tâm O (giả sử điểm có x nhỏ nhất)

- Sắp xếp các điểm còn lại theo góc. Góc của điểm A được tính là góc tạo bởi tia OA với phương ngang.

- Dùng một stack có tính chất ccw của ba điểm liên tiếp theo thứ tự luôn bằng true. Lần lượt chèn các điểm theo thứ tự đã sắp xếp từ đỉnh số 1 đến đỉnh n+1 (quy ước a[n+1]=a[1]). Sau khi chèn điểm a[n+1], stack chứa các thuộc về bao lồi.

Mô tả

bool ccw(ii O, ii A, ii B)

kiểm tra xem B thuộc về nửa mặt phẳng nào (bờ chứa OA). Tức là kiểm tra xem góc AOB là góc dương hay góc âm. Chú ý rằng không được phép gọi ccw nếu O=A hoặc O=B (vì đáp án trả về luôn là false), dẫn đễn việc sort bị sai.

ii origin

tâm để thực hiện sắp xếp điểm theo góc.

Các lỗi thường gặp

Wrong answer

- Đảm bảo lệnh sort góc ở trên là sort(a+2, a+n+1, cmp);.

- Đảm bảo vòng for để nhét các điểm vào stack phải xét cả điểm a[n+1] (chứ không phải là dừng lại ở điểm a[n]). Tức là for (i=1; i<=n+1; i++).