Smallest-circle (1) Emo Welzl

Bài toán

Tìm đường tròn nhỏ nhất chứa tất cả các điểm. Các điểm này nằm trên một mặt phẳng. Số điểm lên tới 100000.

Độ phức tạp

thời gian trung bình O(N)

stack O(N)

bộ nhớ phụ khác không có

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

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

#define long long long

typedef pair<double, double> lflf;

typedef pair<lflf, double> line;

typedef pair<lflf, double> circle;

#define X first

#define Y second

struct random_cmp {

    bool operator()(lflf a, lflf b) { return rand() & 1; }

};

double abs(lflf a) { return sqrt(a.X * a.X + a.Y * a.Y); }

lflf fn(lflf a) { return lflf(-a.Y, a.X); }

lflf operator-(lflf a, lflf b) { return lflf(a.X - b.X, a.Y - b.Y); }

lflf operator+(lflf a, lflf b) { return lflf(a.X + b.X, a.Y + b.Y); }

lflf operator/(lflf a, double x) { return lflf(a.X / x, a.Y / x); }

line xxfd(lflf a, lflf b) {

    lflf n = fn(a - b);

    return line(n, n.X * a.X + n.Y * a.Y);

}

lflf operator*(line a, line b) {

    double D = a.X.X * b.X.Y - a.X.Y * b.X.X;

    double DX = a.Y * b.X.Y - a.X.Y * b.Y;

    double DY = a.X.X * b.Y - a.Y * b.X.X;

    return lflf(DX / D, DY / D);

}

circle circle_through(lflf a, lflf b, lflf c) {

    lflf M = (a + b) / 2, N = (a + c) / 2;

    lflf O = xxfd(M, M + fn(a - b)) * xxfd(N, N + fn(a - c));

    return circle(O, abs(O - a));

}

typedef priority_queue<lflf, vector<lflf>, random_cmp> random_queue;

random_queue qu;

circle smallest_circle(random_queue &qu, vector<lflf> Anchors) {

    if (qu.empty() || Anchors.size() == 3) {

        if (Anchors.size() == 0) return circle(lflf(), -1);

        if (Anchors.size() == 3) return circle_through(Anchors[0], Anchors[1], Anchors[2]);

        lflf A = Anchors.front(), B = Anchors.back();

        return circle((A + B) / 2, abs(A - B) / 2);

    }

    lflf I = qu.top();

    qu.pop();

    circle C = smallest_circle(qu, Anchors);

    if (abs(C.X - I) > C.Y + 1e-9) {

        Anchors.push_back(I);

        C = smallest_circle(qu, Anchors);

    }

    qu.push(I);

    return C;

}

int main() {

    int n;

    scanf("%d", &n);

    if (n == 0) {

        cout << 0 << endl;

        return 0;

    }

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

        int x, y;

        scanf("%d%d", &x, &y);

        qu.push(lflf(x, y));

    }

    circle C = smallest_circle(qu, vector<lflf>());

    cout << fixed;

    cout.precision(2);

    cout << 2 * C.Y << endl;

}

Mô tả

random_queue qu;

là một tập hợp các đỉnh cho phép lấy ra một đỉnh ngẫu nhiên, lưu ý, việc dùng priority_queue như trên làm độ phức tạp tăng lên thành O(n logn), tôi code như trên để cho dễ viết thôi, các bạn có thể dùng vector.

circle circle_through(lflf a, lflf b, lflf c){

trả về đường tròn chứa ba điểm không thẳng hàng

circle smallest_circle(random_queue &qu, vector<lflf> Anchors){

trả về đường tròn chứa các điểm trong qu, và tất cả các điểm trên Anchors phải nằm trên đường tròn.

Thuật toán được trình bày lại như sau:

smallest_circle(S, A):

(trả về đường tròn chứa tất cả các điểm trong S (tức là qu), và tất cả các điểm trong A (tức là Anchors) phải nằm trên đường tròn)

1. nếu S rỗng hoặc A chứa chính xác 3 phần tử thì bài toán đơn giản rồi!

2. ngược lại

3. chọn một đỉnh I ngẫu nhiên trong tập S

4. C := smallest_circle (S-{I}, A)

5. nếu I nằm ngoài đường tròn C thì

6. C := smallest_circle (S-{I}, A+{I})

7. trả về C

Tính chất

Các điểm trong Anchors luôn phân biệt.

Sau lời gọi đệ quy smallest_circle ở bước 4 và bước 6, qu không thay đổi.

Nhận xét

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

Tham khảo

http://www.spoj.com/problems/QCJ4/