Star Way To Heaven 题解

题目链接

分析

此题可以暴力二分，但是只有80pts，所以不采纳这个思想。
考虑与最小生成树的关系，当所有的引力把能走的路全部封死之后，此时的\(ans\)便是最大的引力圈的半径。

step1

首先初始化\(dis[i] = m - y[i]\),把dis[k+1]设为m。

step2

然后用\(Prim\)不停遍历，如果此时找的最近节点为\(k+1\)说明已经遍历完毕，直接退出，
ans更新成ans与dis[falg]之间的大者。
然后更xin\(dis[i](i∈k)\), 更新\(dis[k+1]=min(dis[k+1], y[falg])\)
最后输出\(ans/2\)。

代码

#include <cmath> 
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 6005;
const int MAXM = 1e6 + 5;

int n, m, k;
double x[MAXN], y[MAXN], dis[MAXN], ans;
bool vis[MAXN];

double Dist(int u, int v) {
	return sqrt((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]));
}

int main() {
	scanf ("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= k; i++) {
		scanf ("%lf %lf", &x[i], &y[i]);
		dis[i] = (m * 1.0) - y[i]; 
	}
	dis[k + 1] = m;
	dis[0] = INF;
	ans = -1;
	while (1) {
	        int flag = 0;
		for (int i = 1; i <= k + 1; i++) {
			if (vis[i] == 0 && dis[i] < dis[flag]) flag = i;
		}
		vis[flag] = 1;
		ans = max(ans, dis[flag]);
		if (flag == k + 1) break;
		for (int i = 1; i <= k; i++) {
			dis[i] = min(dis[i], Dist(i, flag));
		}
		dis[k + 1] = min(dis[k + 1], y[flag]);
	} 
	printf ("%.9lf", ans / 2);
	return 0;
}