Submission #935621

#	Time	Username	Problem	Language	Result	Execution time	Memory
935621		ifateen	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	313 ms	496 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    int cc;
    vector<int> par, sz;
    void init(int n) {
        cc = n;
        par.clear(), sz.clear();
        par.resize(n), sz.resize(n, 1);
        iota(begin(par), end(par), 0);
    }
    int get_parent(int u) {
        if (u == par[u]) return u;
        return par[u] = get_parent(par[u]);
    }
    void merge(int a, int b) {
        a = get_parent(a), b = get_parent(b);
        if (a == b) return;
        if (sz[a] > sz[b]) swap(a, b);
        par[a] = b;
        sz[b] += sz[a];
        cc--;
    }
} dsu;
int n;
vector<pair<long double, long double>> points;

bool check(long double mid) {
    long double dist = 4 * mid;
    dsu.init(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long double real_dist = (points[i].first - points[j].first) * (points[i].first - points[j].first) + (points[i].second - points[j].second) * (points[i].second - points[j].second);
            if (real_dist <= dist) dsu.merge(i, j);
        }
    }
    return dsu.cc == 1;
}

void solve() {
    cin >> n;
    points.resize(n);
    for (auto& [x, y] : points) cin >> x >> y;
    long double l = 0, r = 1e18, ans = 1e18;
    for (int i = 0; i < 100; i++) {
        long double mid = (l + r) / 2;
        if (check(mid)) ans = mid, r = mid;
        else l = mid;
    }
    l = 0, r = 1e18;
    for (int i = 0; i < 500; i++) {
        long double mid = (l + r) / 2;
        if (mid * mid <= ans) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(10) << l;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
//    cin >> tc;
    while (tc--) solve();
}

Compilation message (stderr)

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:45:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto& [x, y] : points) cin >> x >> y;
      |                ^

• Subtask 1: 70 / 70