Submission #1318074

#TimeUsernameProblemLanguageResultExecution timeMemory
1318074bshaliOdašiljači (COCI20_odasiljaci)C++17
0 / 70
1096 ms504 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define inf (int)3e18
#define ff first
#define ss second
using vi = vector<int>;
using vii = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 1001;
const long double EPS = 1e-6;

int n;

map<pii, bool> vis;

pii a[MAX];

long double dist(pii a, pii b)
{
    return ((a.ff - b.ff) * (a.ff - b.ff) + (a.ss - b.ss) * (a.ss - b.ss));
}

bool check(long double r)
{
    queue<pii> q;
    q.push(a[1]);

    for (int i = 1; i <= n; i++)
        vis[a[i]] = 0;

    vis[a[1]] = 1;

    while (q.size())
    {
        auto u = q.front();
        q.pop();

        for (int i = 1; i <= n; i++)
        {
            if (vis[a[i]] == 0 && dist(u, a[i]) * dist(u, a[i]) <= 4 * r * r)
            {
                vis[a[i]] = 1;
                q.push(a[i]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (vis[a[i]] == 0)
            return false;

    return true;
}

void solve()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;

        a[i].ff = u, a[i].ss = v;
    }

    long double l = 0, r = 1e9 + 5, m = 0, ans = 12;

    while (r - l > EPS)
    {
        m = (l + r) / 2;

        if (check(m))
        {
            ans = m;
            r = m;
        }
        else
        {
            l = m;
        }
    }

    cout << fixed << setprecision(7) << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;
    while (tt--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...