//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
struct DSU {
vector <int> par;
DSU(int n) {
par.resize(n);
iota(par.begin(), par.end(), 0ll);
}
inline bool same(int a, int b) {
return get(a) == get(b);
}
inline int get(int a) {
return par[a] = (par[a] == a ? a : get(par[a]));
}
inline bool unite(int a, int b) {
if(same(a, b))
return false;
a = get(a), b = get(b);
par[a] = b;
return true;
}
};
double sq(double a) {
return a * a;
}
#define ONLINE_JUDGE
void solve() {
int n;
cin >> n;
pair <int, int> arr[n];
for(auto &[a, b] : arr) {
cin >> a >> b;
}
auto check = [&](double mid) -> bool {
DSU dsu(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
double dist = sq(arr[i].first - arr[j].first) + sq(arr[i].second - arr[j].second);
if(dist <= sq(mid)) {
dsu.unite(i, j);
}
}
}
bool ok = true;
for(int i = 0; i +1 < n; i++) {
ok &= dsu.get(i) == dsu.get(i +1);
}
return ok;
};
double l = 0, r = 3e9;
while(r - l >= 1e-6) {
double mid = (l + r) / 2;
if(check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << setprecision(9) << l / 2;
//cerr << l << " " << r << "\n";
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
600 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
47 ms |
348 KB |
Output is correct |
| 7 |
Correct |
47 ms |
348 KB |
Output is correct |
| 8 |
Correct |
110 ms |
460 KB |
Output is correct |
| 9 |
Correct |
130 ms |
600 KB |
Output is correct |
| 10 |
Correct |
94 ms |
484 KB |
Output is correct |
