oj.uz

답안 #935621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935621 2024-02-29T09:51:47 Z ifateen Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 313 ms 496 KB 
#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

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.0 / 70.0

# 결과 실행 시간 메모리 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 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 86 ms 348 KB Output is correct
7 Correct 101 ms 348 KB Output is correct
8 Correct 188 ms 344 KB Output is correct
9 Correct 313 ms 492 KB Output is correct
10 Correct 299 ms 496 KB Output is correct