发表时间:2014-09-05来源:网络
#include<iostream> #include<cmath> #include<iomanip> #include<cstring> #include<float.h> using 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;k<cur;k++) { if (center[k]+size[Put[k]]>maxsize) maxsize=center[k]+size[Put[k]]; } if (maxsize<MinL) MinL=maxsize; } else { for (i=0;i<m;i++) { if (!vis[i]) { Put[cur]=i; vis[i]=1; double tmpl; bool ok=1; for (j=cur-1;j>=0;j--) { tmpl=getlen(Put[j],i); center[cur]=center[j]+tmpl; if (center[cur]-size[Put[cur]]<0) {ok=0;break;} if (isok(cur,j)) break; } if (ok) dfs(cur+1); vis[i]=0; } } } } int main() { int n; cin>>n; while(n--) { cin>>m; MinL=DBL_MAX; memset(vis,0,sizeof(vis)); for (int i=0;i<m;i++) cin>>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; }
CI框架连接数据库配置操作以及多数据库操作
asp 简单读取数据表并列出来 ASP如何快速从数据库读取大量数据
C语言关键字及其解释介绍 C语言32个关键字详解
C语言中sizeof是什么意思 c语言里sizeof怎样用法详解
将视频设置为Android手机开机动画的教程
IcePHP框架中的快速后台中的通用CRUD功能框架
java中的info是什么意思
PHP中include和require区别之我见
PHP中的魔术方法 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, __unset , __sleep,
PHP中的(++i)前缀自增 和 (i++)后缀自增
2014-09-05
2014-09-05
2022-03-22
2014-09-05
2022-03-17
2017-05-10
2022-03-17
2014-09-05
2022-03-21
2022-03-22