圆排列问题

class Circle {
    friend float CirclePerm(int, float*);
private:
    float Center(int t);
    void Compute(void);
    void Backtrack(int t);
    float min, *x, *r;
    int n;
};

float Circle::Center(int t) {
    float temp = 0;
    for (int j = 1; j < t; j++) {
        float valuex = x[j] + 2 * sqrt(r[j] * r[t]);
        if (valuex > temp) {
            temp = valuex;
        }
    }
    return temp;
}

void Circle::Compute(void) {
    float low = 0, high = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i] - r[i] < low) {
            low = x[i] - r[i];
        }
        if (x[i] + r[i] > high) {
            high = x[i] + r[i];
        }
    }
    if (high - low < min) {
        min = high - low;
    }
}

void Circle::Backtrack(int t) {
    if (t > n)
        Compute();
    else {
        for (int j = t; j <= n; j++) {
            Swap(r[t], r[j]);
            float centerx = Center(t);
            if (centerx + r[t] + r[1] < min) {
                x[t] = centerx;
                Backtrack(t + 1);
            }
            Swap(r[t], r[j]);
        }
    }
}

float CirclePerm(int n, float *a) {
    Circle X;
    X.n = n;
    X.r = a;
    X.min = 100000;
    X.x = new float[n + 1];
    X.Backtrack(1);
    delete [] X.x;
    return X.min;
}

最后更新: 2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
回到页面顶部