Submission #1340059

#TimeUsernameProblemLanguageResultExecution timeMemory
1340059ZeroOdašiljači (COCI20_odasiljaci)C++20
70 / 70
143 ms25232 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pi pair<int,int>

struct tr{
    int u, v, w;
};

bool cp(tr a, tr b){
    if(a.w == b.w) return a.u < b.u;
    return a.w < b.w;
}

int ds(pi a, pi b){
    return (a.ff - b.ff) * (a.ff-b.ff) + (a.ss - b.ss) * (a.ss-b.ss);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    
    int n; cin >> n;
    vector<pi> a(n);
    vector<int> trid(n+1);
    for(int i=0; i < n; i ++) trid[i] = i;

    for(auto &i : a) cin >>i.ff >> i.ss;
    
    vector<tr> b;
    for(int i=0; i < n; i ++){
        for(int j=0; j < n; j ++){
            if(j == i) continue;

            int y = ds(a[i], a[j]);
            b.pb({i,j,y});
        }
    }

    sort(b.begin(),b.end(),cp);
    int mx = 0;

    for(auto i : b){
        if(trid[i.u] != trid[i.v]){
            mx = max(mx, i.w);
            int ol = trid[i.u], nw = trid[i.v];
            for(int i=0; i < n; i ++) if(trid[i] == ol) trid[i] = nw;
        }
    }

    double t = sqrt(mx);
    t /= double(2);
    cout << fixed << setprecision(12) << t;



}

#Verdict Execution timeMemoryGrader output
Fetching results...