# 【题解】Star Way To Heaven()-其他

## 【题解】Star Way To Heaven()

10 5 2
1 1
2 3

1.118033989

10 5 2
1 1
2 3

10 5 2
1 1
2 3

1.118033989

1.118033989

### Code

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXN = 6005, INF = 1e9;
int n, m, k;
double x[MAXN], y[MAXN], dis[MAXN], ans;
bool vis[MAXN];
double Dis(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
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 - y[i];
}
k++;
dis[k] = m;
while (1) {
int p = -1;
for (int i = 1; i <= k; i++)
if (!vis[i] && (p == -1 || dis[i] < dis[p]))
p = i;
if (p == -1)
continue;
vis[p] = 1;
ans = max(ans, dis[p]);
if (p == k)
break;
for (int i = 1; i < k; i++)
dis[i] = min(dis[i], Dis(i, p));
dis[k] = min(dis[k], y[p]);
}
printf("%.9lf", ans * 0.5);
return 0;
}

————————

10 5 2
1 1
2 3

1.118033989

10 5 2
1 1
2 3

10 5 2
1 1
2 3

1.118033989

1.118033989

### Code

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXN = 6005, INF = 1e9;
int n, m, k;
double x[MAXN], y[MAXN], dis[MAXN], ans;
bool vis[MAXN];
double Dis(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
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 - y[i];
}
k++;
dis[k] = m;
while (1) {
int p = -1;
for (int i = 1; i <= k; i++)
if (!vis[i] && (p == -1 || dis[i] < dis[p]))
p = i;
if (p == -1)
continue;
vis[p] = 1;
ans = max(ans, dis[p]);
if (p == k)
break;
for (int i = 1; i < k; i++)
dis[i] = min(dis[i], Dis(i, p));
dis[k] = min(dis[k], y[p]);
}
printf("%.9lf", ans * 0.5);
return 0;
}