圆排列问题
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
创建日期: 2024年1月2日 19:47:42