poj Building a Space Station
2024-08-25 03:57:43
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 ;
}
最新文章
- MVC通过路由实现URL重写
- vs2015 HTTP Error 400. The request hostname is invalid.
- [资料分享]dubbo视频教程流行版
- Jmeter 使用Jmeter与Badboy进行压力测试
- sublime配置markdown
- EditText自定义边框
- App Icon生成工具(转载)
- 进制格式转换 c#
- UVA 11076 Add Again 计算对答案的贡献+组合数学
- Codeforces Round #215 (Div. 1) B. Sereja ans Anagrams 匹配
- 【学习笔记】【C语言】变量
- Executors 构建线程池
- Oracle实践--PL/SQL表分区的基础
- [ios2]iphone编程中使用封装的NSLog来打印调试信息 【转】
- 游戏UI框架设计(三) : 窗体的层级管理
- 20160215.CCPP体系详解(0025天)
- php优秀框架codeigniter学习系列——CI_Loader类分析
- 【剑指Offer】只出现一次的字符
- Vmware Workstation _linux yum 仓库搭建
- Win#password;;processon #clone;;disassemble;;source find
热门文章
- rsyslog 报 WARNING: rsyslogd is running in compatibility mode.
- phpcms如何嵌套循环
- C# 读取XML文件示例
- centos 安装 lnmp
- codevs 1725 探险 (二分)
- jQuery的css()方法
- request.getAttribute( ";result";);和request.setAttribute(";result";,username);
- XML参数转换为Object,并转换为List或DataTable
- oracle 添加表分区
- Oracle10g、 Oracle11g完美共存