1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1100; const double eps=1e-8; struct node{double x,y,z;}p[N]; int n; double a[N][N],b[N][N],d[N];int v[N];//a为高度,b为长度 double dis(node n1,node n2){return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));} bool prim(double L){ memset(d,0x7f,sizeof(d));d[1]=0;//memset double 0 为 0,0x7f为无穷大。其他都不能用。 memset(v,0,sizeof(v)); for(int i=1;i<=n;i++){ int x=0; for(int j=1;j<=n;j++){ if(!v[j]&&(x==0||d[j]<d[x]))x=j; } v[x]=1; for(int y=1;y<=n;y++) if(!v[y]&&d[y]>a[x][y]-L*b[x][y]) d[y]=a[x][y]-L*b[x][y]; } double ans=0;for(int i=2;i<=n;i++)ans+=d[i]; return ans>=0.0; } int main(){ while(scanf("%d",&n)!=EOF&&n) { for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) { a[i][j]=abs(p[i].z-p[j].z); b[i][j]=dis(p[i],p[j]); } double l=0,r=1e9,mid; while(r-l>eps) { mid=(l+r)/2; if(prim(mid))l=mid; else r=mid; } printf("%.3lf\n",l); } return 0; }
- 1
信息
- ID
- 1436
- 时间
- 10000ms
- 内存
- 64MiB
- 难度
- 8
- 标签
- 递交数
- 146
- 已通过
- 20
- 上传者