记录编号	563401	评测结果	AAAAAAAAAA
题目名称	[POJ 2728]沙漠之王	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.965 s
提交时间	2021-08-05 20:32:47	内存使用	13.45 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
#define RE register
using namespace std;
const double eps = 1e-6;
const int maxn = 1005;
int n;
double x[maxn],y[maxn];
double height[maxn];
double dist(int i,int j) {
	return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
bool vis[maxn];
double dis[maxn];
double h[maxn][maxn],d[maxn][maxn],mp[maxn][maxn];
double solve(double rate) {
	double ans = 0;
	memset(vis , false , sizeof(vis));
	for(RE int i = 1;i <= n + 1;++ i)dis[i] = 1e15;
	for(RE int i = 1;i <= n;++ i) {
		for(RE int j = 1;j < i;++ j) {
			mp[i][j] = mp[j][i] = h[i][j] - rate * d[i][j];
		}
	}
	dis[1] = 0;
	for(int q = 1;q <= n;++ q) {
		int u = n + 1;
		for(int i = 1;i <= n;++ i) {
			if(!vis[i]&&dis[i] != 1e15&&dis[i] < dis[u])u = i;;
		}
		vis[u] = true;
		ans += dis[u];
		for(RE int i = 1;i <= n;++ i) {
			int v = i;
			double w = h[u][v] - rate * d[u][v];
			if(!vis[v]&&dis[v] > w) {
				dis[v] = w;                
			}
		}
	}
	return ans;
}
void work() {
	for(RE int i = 1;i <= n;++ i) {
		scanf("%lf%lf%lf",&x[i],&y[i],&height[i]);
	}
	for(RE int i = 1;i <= n;++ i) {
		for(RE int j = 1;j < i;++ j) {
			h[i][j] = h[j][i] = abs(height[i] - height[j]);
			d[i][j] = d[j][i] = dist(i , j);
		}                                                     
	}
	double l = 0,r = 1e5,mid; 
	while(r - l > eps) {        
		mid = (l + r) / 2;
		if(solve(mid) < 0)r = mid;
		else l = mid;
	}
	printf("%.3lf\n",mid);
	return ;
}
int main() {
	freopen("desertking.in","r",stdin);
	freopen("desertking.out","w",stdout);
	while(~ scanf("%d",&n)) {
		if(!n)break ;
		work();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}