#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define lowbit(x) x & (-x);
#define inf 1e18
#define _inf -1e18
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define inv(a) for (int& x: a) cin >> x
#define pri(a) for (int& x: a) cout << x << ' '
int const MOD = 998244353;
int const lg = 20;
int const block = 500;
// int block;
int const MAX = 1e3 + 1, N = 20;
int n, m, q, k, p;
void bexuyen67() {
cin >> n;
vector<pair<double, double>> a(n);
for (auto& it: a)
cin >> it.first >> it.second;
double l = 0, r = 1e9;
double res;
auto dis = [&](pair<double, double> a, pair<double, double> b){
double x = (a.first - b.first) * (a.first - b.first);
double y = (a.second - b.second) * (a.second - b.second);
return sqrt(x + y);
};
vector<bool> vs(n);
auto dfs = [&](auto binh, int u, vector<vector<int>>& g) -> void{
vs[u] = 1;
for (int v: g[u]){
if (!vs[v])
binh(binh, v, g);
}
};
auto can = [&](double mid){
vector<vector<int>> g(n);
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (dis(a[i], a[j]) <= mid*2.0){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
fill(all(vs), 0);
dfs(dfs, 0, g);
for (int i = 0; i < n; i++)
if (!vs[i])
return false;
return true;
};
// cout << can(0.7071068);
for (int t = 0; t < 100; t++){
double mid = (l + r)/2;
if (can(mid)){
r = mid;
res = mid;
}
else l = mid;
}
cout << res;
}
signed main() {
#ifdef binhball
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(15);
int t = 1;
// cin >> t;
while (t--)
bexuyen67();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
3 ms |
516 KB |
Output is correct |
| 4 |
Correct |
5 ms |
348 KB |
Output is correct |
| 5 |
Correct |
6 ms |
600 KB |
Output is correct |
| 6 |
Correct |
135 ms |
2624 KB |
Output is correct |
| 7 |
Correct |
136 ms |
2624 KB |
Output is correct |
| 8 |
Correct |
318 ms |
6720 KB |
Output is correct |
| 9 |
Correct |
456 ms |
9092 KB |
Output is correct |
| 10 |
Correct |
422 ms |
9048 KB |
Output is correct |
