#include <bits/stdc++.h>
#define print(x) cout << #x <<" = " << x << endl
#define pprint(x) cout << #x <<" = (" << x.first << " , " << x.second <<" )\n"
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / b)
#define all(x) x.begin(), x.end()
#define MAXN 1000005
#define INF 1000000000000000
#define MOD 1000000007
#define eps (1e-8)
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
struct pt {
lld x, y;
};
int n;
vector<pt> a;
vector<int> par, rk;
lld dis(pt a, pt b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init() {
rep(i, 1, n) par[i] = i, rk[i] = 0;
}
int find_par(int a) {
if(par[par[a]] == par[a]) return par[a];
else return find_par(par[a]);
}
void unite(int a, int b) {
int aa = find_par(a), bb = find_par(b);
if(aa == bb) return;
if(rk[aa] > rk[bb]) par[bb] = aa;
else if(rk[bb] > rk[aa]) par[aa] = bb;
else par[bb] = aa, rk[aa] ++;
return;
}
bool check(lld x) {
init();
rep(i, 1, n) rep(j, i + 1, n) {
if(dis(a[i], a[j]) <= 2 * x) unite(i, j);
}
int aa = find_par(1);
rep(i, 1, n) if(find_par(i) != aa) return false;
return true;
}
lld solve() {
lld l = 0, r = INF;
while(r - l > eps) {
lld mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
return r;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n, a.resize(n + 1);
par.resize(n + 1), rk.resize(n + 1);
rep(i, 1, n) cin >> a[i].x >> a[i].y;
cout << fixed << setprecision(7) << solve() <<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
5 ms |
364 KB |
Output is correct |
| 5 |
Correct |
7 ms |
364 KB |
Output is correct |
| 6 |
Correct |
181 ms |
492 KB |
Output is correct |
| 7 |
Correct |
180 ms |
364 KB |
Output is correct |
| 8 |
Correct |
399 ms |
492 KB |
Output is correct |
| 9 |
Correct |
648 ms |
640 KB |
Output is correct |
| 10 |
Correct |
606 ms |
492 KB |
Output is correct |
