Submission #935055

#	Time	Username	Problem	Language	Result	Execution time	Memory
935055		Omar_G	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	63 ms	14280 KiB

odasiljaci

#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;
}

• Subtask 1: 70 / 70