| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
爽爽爽#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const double eps=1e-6;
int n,x[N],y[N],z[N];
double c[N][N],l[N][N],d[N];
bool v[N];
bool chk(double m){
for(int i=1;i<=n;i++)d[i]=1e18,v[i]=0;
d[1]=0;
double s=0;
for(int i=1;i<=n;i++){
int u=-1;
for(int j=1;j<=n;j++)if(!v[j]&&(u==-1||d[j]<d[u]))u=j;
v[u]=1;s+=d[u];
for(int j=1;j<=n;j++)if(!v[j])d[j]=min(d[j],c[u][j]-m*l[u][j]);
}
return s>=0;
}
int main(){
//freopen("desertking.in","r",stdin);
//freopen("desertking.out","w",stdout);
while(scanf("%d",&n),n){
for(int i=1;i<=n;i++)scanf("%d%d%d",&x[i],&y[i],&z[i]);
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
c[i][j]=c[j][i]=fabs(z[i]-z[j]);
l[i][j]=l[j][i]=hypot(x[i]-x[j],y[i]-y[j]);
}
double L=0,R=100;
while(R-L>eps){
double M=(L+R)/2;
if(chk(M))L=M;
else R=M;
}
printf("%.3f\n",L);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator