soj1740排列树回溯.cpp

一些ACM题目的解答,主要是soj和poj的

#include<cstdio>
#include<cmath>

double x[10];
double radius[10];
double min;
int n;

void Swap(double &a,double &b)
{
    double t = a;
    a=b;
    b=t;
}

double center(int t)
{
    double result = 0;
    int i;
    for( i=0 ;i<t;i++)
    {
        double valuex = x[i] + 2.0 * sqrt(radius[i]*radius[t]);
        if(valuex > result)
            result = valuex;
    }
    return result;
}
void Compute(void)
{
    double low =0, high=0;
    for(int i=0;i<n;i++)
    {
        if(x[i]-radius[i]<low)
            low=x[i]-radius[i];
        if(x[i]+radius[i]>high)
            high=x[i]+radius[i];
    }
    if(high-low<min)
        min=high-low;
}

void backtrack(int t)
{
    if(t>=n)
        Compute();
    else
        for(int j=t;j<n;j++)
        {
            Swap(radius[j],radius[t]);
            double centerx = center(t);
            if(centerx+radius[t]+radius[0]<min)
            {
                x[t]=centerx;
                backtrack(t+1);
            }
            Swap(radius[t],radius[j]);
        }
}
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int i;
        for(i=0;i<n;i++)
            scanf("%lf",&radius[i]);
        min = 1e200;
        backtrack(0);
        printf("%.3lf\n",min);
    }
    return 0;
}