제출 #1333513

#제출 시각아이디문제언어결과실행 시간메모리
1333513luhoaithuongOdašiljači (COCI20_odasiljaci)C++20
70 / 70
124 ms488 KiB
#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define fi first
#define se second
#define int long long
#define ldb long double
using namespace std;
const int MAXN = 1005;
ldb x[MAXN], y[MAXN];
int par[MAXN], sz[MAXN], n;
ldb dist(int i, int j) {
    return sqrtl((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
void build() {
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
}
int findP(int i) {
    if (i == par[i]) return i;
    return par[i] = findP(par[i]);
}
void Union(int u, int v) {
    u = findP(u);
    v = findP(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
    // cout << sz[v] << " BIchup\n";
}
bool check(ldb r) {
    build();
    vector<pii> e;
    // cout << fixed << setprecision(7) << r << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            ldb d = dist(i, j);
            // cout << i << ' ' << j << ' ' << d << '\n';
            if (d <= (ldb)2.0 * r) Union(i, j);
        }
    // cout << "-------\n";
    if (sz[findP(1)] == n) return 1;
    return 0;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    ldb l = 0, r = 1e9, res, mid;
    while ((r - l) >= 1e-9) {
        mid = (l + r) / 2;
        if (check(mid))
            res = mid, r = mid;
        else
            l = mid;
    }
    cout << fixed << setprecision(8) << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...