#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int cc;
vector<int> par, sz;
void init(int n) {
cc = n;
par.clear(), sz.clear();
par.resize(n), sz.resize(n, 1);
iota(begin(par), end(par), 0);
}
int get_parent(int u) {
if (u == par[u]) return u;
return par[u] = get_parent(par[u]);
}
void merge(int a, int b) {
a = get_parent(a), b = get_parent(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
par[a] = b;
sz[b] += sz[a];
cc--;
}
} dsu;
int n;
vector<pair<long double, long double>> points;
bool check(long double mid) {
long double dist = 4 * mid;
dsu.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long double real_dist = (points[i].first - points[j].first) * (points[i].first - points[j].first) + (points[i].second - points[j].second) * (points[i].second - points[j].second);
if (real_dist <= dist) dsu.merge(i, j);
}
}
return dsu.cc == 1;
}
void solve() {
cin >> n;
points.resize(n);
for (auto& [x, y] : points) cin >> x >> y;
long double l = 0, r = 1e18, ans = 1e18;
for (int i = 0; i < 100; i++) {
long double mid = (l + r) / 2;
if (check(mid)) ans = mid, r = mid;
else l = mid;
}
l = 0, r = 1e18;
for (int i = 0; i < 500; i++) {
long double mid = (l + r) / 2;
if (mid * mid <= ans) l = mid;
else r = mid;
}
cout << fixed << setprecision(10) << l;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tc = 1;
// cin >> tc;
while (tc--) solve();
}
Compilation message
odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:45:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for (auto& [x, y] : points) cin >> x >> y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
348 KB |
Output is correct |
| 6 |
Correct |
86 ms |
348 KB |
Output is correct |
| 7 |
Correct |
101 ms |
348 KB |
Output is correct |
| 8 |
Correct |
188 ms |
344 KB |
Output is correct |
| 9 |
Correct |
313 ms |
492 KB |
Output is correct |
| 10 |
Correct |
299 ms |
496 KB |
Output is correct |
