uva10012 はあなたが思っているほど単純ではありません

#include#include#include#include#includeusing namespace std;  
  
int m,Put[10];          //Put[i]:放置的第i个圆的编号  
double MinL,size[10],center[10];//size[i]:编号为i的圆的半径；center[i]:放置的第i个圆的圆心位置  
bool vis[10];  
  
double getlen(int a,int b)      //计算两圆心间的距离  
{  
    return sqrt((size[a]+size[b])*(size[a]+size[b])-(size[a]-size[b])*(size[a]-size[b]));  
}  
bool isok(int a,int b)          //是否和之前放的圆相交  
{  
    for (int i=0;i<b;i++)  
    {  
        if (sqrt((center[i]-center[a])*(center[i]-center[a])+(size[Put[i]]-size[Put[a]])*(size[Put[i]]-size[Put[a]]))<(size[Put[i]]+size[Put[a]]))  
            return false;  
    }  
    return true;  
}  
void dfs(int cur)  
{  
    int i,j;  
    if (cur==m)  
    {     
        double maxsize=0;  
        for (int k=0;kmaxsize)  
                maxsize=center[k]+size[Put[k]];  
        }  
        if (maxsize<MinL)  
            MinL=maxsize;  
    }  
    else  
    {  
        for (i=0;i=0;j--)  
                {  
                    tmpl=getlen(Put[j],i);  
                    center[cur]=center[j]+tmpl;  
                    if (center[cur]-size[Put[cur]]>n;  
    while(n--)  
    {  
        cin>>m;  
        MinL=DBL_MAX;  
        memset(vis,0,sizeof(vis));  
        for (int i=0;i>size[i];  
        for (int i=0;i<m;i++)  
        {  
            Put[0]=i;  
            center[0]=size[i];  
            vis[i]=1;  
            dfs(1);  
            vis[i]=0;  
        }  
        cout<<fixed<<setprecision(3)<<MinL<<endl;  
    }  
    return 0;  
}