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++ ,