http://poj.org/problem?id=2031

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const double eps=1e-;
const int inf=<<;
int cmp(double x)
{
if(fabs(x)<eps) return ;
if(x>) return ;
return -;
} const double pi=acos(-1.0);
inline double sqr(double x)
{
return x*x;
} inline double Sqrt(double a)
{
return a<=?:sqrt(a);
} struct point
{
double x,y,z,r;
point(){}
point(double a,double b,double c,double d):x(a),y(b),z(c),r(d){}
}; double dis(const point &a,const point &b)
{
return Sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z));
} double dist[];
double diss[][],ans;
bool vis[];
bool prime(int n)
{
memset(vis,,sizeof(vis));
for(int i=; i<=n; i++)
dist[i]=inf;
ans=;dist[]=;
for(int i=; i<=n; i++){
double temp=inf;
int k=;
for(int j=; j<=n; j++)
{
if(!vis[j]&&dist[j]<temp)
{
temp=dist[j];
k=j;
}
}
if(temp==inf) return false;
vis[k]=true;
ans+=temp;
for(int j=; j<=n; j++)
{
if(!vis[j]&&dist[j]>diss[k][j])
{
dist[j]=diss[k][j];
}
}
}
return true;
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
point a[];
memset(diss,,sizeof(diss));
for(int i=; i<=n; i++)
{
scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
}
memset(diss,,sizeof(diss));
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(dis(a[i],a[j])-a[i].r-a[j].r<=)
diss[i][j]=;
else if(dis(a[i],a[j])-a[i].r-a[j].r>eps)
diss[i][j]=dis(a[i],a[j])-a[i].r-a[j].r;
}
}
prime(n);
printf("%.3lf\n",ans);
}
return ;
}

最新文章

  1. MVC通过路由实现URL重写
  2. vs2015 HTTP Error 400. The request hostname is invalid.
  3. [资料分享]dubbo视频教程流行版
  4. Jmeter 使用Jmeter与Badboy进行压力测试
  5. sublime配置markdown
  6. EditText自定义边框
  7. App Icon生成工具(转载)
  8. 进制格式转换 c#
  9. UVA 11076 Add Again 计算对答案的贡献+组合数学
  10. Codeforces Round #215 (Div. 1) B. Sereja ans Anagrams 匹配
  11. 【学习笔记】【C语言】变量
  12. Executors 构建线程池
  13. Oracle实践--PL/SQL表分区的基础
  14. [ios2]iphone编程中使用封装的NSLog来打印调试信息 【转】
  15. 游戏UI框架设计(三) : 窗体的层级管理
  16. 20160215.CCPP体系详解(0025天)
  17. php优秀框架codeigniter学习系列——CI_Loader类分析
  18. 【剑指Offer】只出现一次的字符
  19. Vmware Workstation _linux yum 仓库搭建
  20. Win#password;;processon #clone;;disassemble;;source find

热门文章

  1. rsyslog 报 WARNING: rsyslogd is running in compatibility mode.
  2. phpcms如何嵌套循环
  3. C# 读取XML文件示例
  4. centos 安装 lnmp
  5. codevs 1725 探险 (二分)
  6. jQuery的css()方法
  7. request.getAttribute( &quot;result&quot;);和request.setAttribute(&quot;result&quot;,username);
  8. XML参数转换为Object,并转换为List或DataTable
  9. oracle 添加表分区
  10. Oracle10g、 Oracle11g完美共存