1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e3+7;
const double esp=1e-5;
struct {int x,y,z;}mp[N];
double a[N][N],b[N][N],c[N][N],dis[N];
int n,vis[N];
inline void init(){
rep(i,1,n)scanf("%d%d%d",&mp[i].x,&mp[i].y,&mp[i].z);
rep(i,1,n)rep(j,i+1,n){
a[i][j]=a[j][i]=abs(mp[i].z-mp[j].z);
b[i][j]=b[j][i]=sqrt(1.0*(mp[i].x-mp[j].x)*(mp[i].x-mp[j].x)+1.0*(mp[i].y-mp[j].y)*(mp[i].y-mp[j].y));
}
}
double check(double x){
double res=0;
memset(vis,0,sizeof vis);
rep(i,1,n)rep(j,i+1,n)c[i][j]=c[j][i]=a[i][j]-x*b[i][j];
rep(i,1,n)dis[i]=c[1][i];
vis[1]=1;
rep(i,2,n){
int k;
double mn=1.0*0x3f3f3f3f;
rep(j,1,n)if(!vis[j]&&mn>dis[j]){mn=dis[j];k=j;}
res+=mn;vis[k]=1;
rep(j,1,n)if(!vis[j]&&dis[j]>c[k][j])dis[j]=c[k][j];
}
return res;
}
double find(){
double l=0,r=1.0*0x3f3f3f3f;
while(l+esp<r){
double mid=(l+r)/2;
if(check(mid)<=0)r=mid;
else l=mid;
}
return l;
}
int main(){
while(~scanf("%d",&n)&&n){
init();
double ans=find();
printf("%.3fn",ans);
}
return 0;
}
|
近期评论