当前位置:编程学习 > C/C++ >>

10012 - How Big Is It?

[cpp]
描述:好麻烦的题目,准确的说就是给定m个圆的半径, 
现在要求找到一个矩形使得每一个球都以地面相切, 
要求输出最小的矩阵的长度 
#include <cstdio> 
#include <cmath> 
#include <cstring> 
int n,m,j,flag[12]; 
double count,num[10],p[10],value[10]; 
void dfs(int cur,double x,double y) 

    if(cur>=m) 
    { 
        if(!flag[10]) count=y-x; 
        else if(y-x<count) count=y-x; 
        flag[10]=1; 
        return ; 
    } 
    for(int i=0; i<m; i++) 
        if(!flag[i]) 
        { 
            flag[i]=1; 
            p[cur]=num[i]; 
            value[cur]=0; 
            for (j=0; j<cur; j++) 
            { 
                double c=sqrt((p[cur]+p[j])*(p[cur]+p[j])-(p[cur]-p[j])*(p[cur]-p[j]))+value[j]; 
                if (c>value[cur]) value[cur]=c; 
            } 
            double a,b; 
            if(value[cur]-p[cur]<x) a=value[cur]-p[cur]; 
            else a=x; 
            if(value[cur]+p[cur]>y) b=value[cur]+p[cur]; 
            else b=y; 
            dfs(cur+1,a,b); 
            flag[i]=0; 
        } 

int main() 

#ifndef ONLINE_JUDGE 
    freopen("a.txt","r",stdin); 
#endif 
    scanf("%d",&n); 
    while(n--) 
    { 
        scanf("%d",&m); 
        count=0; 
        for(int i=0; i<m; i++) scanf("%lf",&num[i]); 
        memset(flag,0,sizeof(flag)); 
        memset(value,0,sizeof(value)); 
        if(m>1) for(int i=0; i<m; i++) 
            { 
                flag[i]=1; 
                value[0]=p[0]=num[i]; 
                double a=value[0]-p[0]; 
                double b=value[0]+p[0]; 
                dfs(1,a,b); 
                flag[i]=0; 
            } 
        else count=2*num[0]; 
        printf("%.3lf\n",count); 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,