#include <bits/stdc++.h>
using namespace std;
#define ll /*Omar-G*/ long long
#define endl/*Omar-G*/ "\n"
const ll mod = 1e9 + 7, N = 1e3 + 5;
vector <ll> d(N);
ll f(ll x) {
if (d[x] == x) return x;
return d[x] = f(d[x]);
}
void u(ll x, ll y) {
d[f(x)] = f(y);
}
void solve() {
ll n; cin >> n;
vector <pair<pair<ll,ll>,double>> a;
vector <ll> x(n+5), y(n+5);
for (ll i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
for (ll i = 1; i <= n; i++) {
for (ll j = 1 + i; j <= n; j++) {
ll dx = x[i] - x[j];
ll dy = y[i] - y[j];
a.push_back({{i, j}, sqrt(dx*dx + dy*dy)});
}
}
double l = 0, r = 1e9, s = 1e-8;
cout << setprecision(10);
while (l <= r) {
double v = (l + r) / 2;
for (ll i = 1; i <= n; i++) d[i] = i;
for (auto i : a) {
if (i.second <= v * 2) u(i.first.first, i.first.second);
}
ll c = 1;
for (ll i = 1; i <= n; i++) {
c &= (f(i) == f(1));
}
if (c) r = v - s;
else l = v + s;
}
cout << l << endl;
}
void solveT() {ll t; cin >> t; while (t--) solve();}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
| # |
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 |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
600 KB |
Output is correct |
| 6 |
Correct |
23 ms |
4300 KB |
Output is correct |
| 7 |
Correct |
24 ms |
4048 KB |
Output is correct |
| 8 |
Correct |
53 ms |
13632 KB |
Output is correct |
| 9 |
Correct |
63 ms |
14280 KB |
Output is correct |
| 10 |
Correct |
44 ms |
14244 KB |
Output is correct |
