제출 #513030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513030		KoD	Odašiljači (COCI20_odasiljaci)	C++17	49 / 70	1084 ms	308 KiB

odasiljaci

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<double> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i];
    }
    const auto check = [&](const double thres) {
        vector<char> reach(N);
        std::queue<int> que;
        const auto push = [&](const int u) {
            if (!reach[u]) {
                reach[u] = true;
                que.push(u);
            }
        };
        push(0);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int v = 0; v < N; ++v) {
                if (std::hypot(X[u] - X[v], Y[u]- Y[v]) <= 2.0 * thres) {
                    push(v);
                }
            }
        }
        return std::count(reach.begin(), reach.end(), true) == N;
    };
    double ok = 2.0 * 1e9, ng = 0.0;
    for (int step = 0; step < 50; ++step) {
        const double md = (ok + ng) / 2.0;
        (check(md) ? ok : ng) = md;
    }
    std::cout << std::fixed << std::setprecision(20);
    std::cout << ok << '\n';
    return 0;
}

• Subtask 1: 49 / 70