Submission #1321100

#TimeUsernameProblemLanguageResultExecution timeMemory
1321100suleyman_1951Odašiljači (COCI20_odasiljaci)C++20
42 / 70
655 ms4184 KiB
// TEMPLATE
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_set_char tree<char, null_type, less<char>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_set_string tree<string, null_type, less<string>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset_char tree<char, null_type, less_equal<char>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset_string tree<string, null_type, less_equal<string>, rb_tree_tag, tree_order_statistics_node_update>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
#define ldouble long double
#define ll unsigned long long
// #define int int_fast32_t
#define endl '\n'
#define pii pair<int, int>
#define F first
#define S second
void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> vt;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        vt.push_back({a, b});
    }
    double l = 0.0, r = 1e15, ans = 0.0;
    for (int k = 1; k <= 105; k++)
    {
        double d = 1.0 * (l + r) / 2;
        vector<int> adj[n + 5];
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                pii o = vt[i - 1], p = vt[j - 1];
                if (sqrt(abs(o.first - p.first) * abs(o.first - p.first) + abs(o.second - p.second) * abs(o.second - p.second)) / 2 <= d)
                {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        vector<int> dis(n + 5, -1);
        queue<int> q;
        q.push(1);
        dis[1] = 0;
        while (q.size())
        {
            int x = q.front();
            q.pop();
            for (int i : adj[x])
            {
                if (dis[i] == -1)
                {
                    q.push(i);
                    dis[i] = dis[x] + 1;
                }
            }
        }
        bool ok = true;
        for (int i = 1; i <= n; i++)
        {
            if (dis[i] == -1)
            {
                ok = false;
            }
        }
        if (ok)
        {
            ans = d;
            r = d;
        }
        else
        {
            l = d;
        }
    }
    cout << setprecision(7) << fixed << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...