Submission #336185

#	Time	Username	Problem	Language	Result	Execution time	Memory
336185		wiwiho	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	69 ms	8668 KiB

odasiljaci

#include<bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define lsort(a) sort(iter(a))
#define eb emplace_back

using namespace std;

typedef long long ll;

vector<int> dsu;

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}

void unionDSU(int a, int b){
    a = findDSU(a);
    b = findDSU(b);
    dsu[b] = a;
}

ll dis(pll a, pll b){
    ll x = a.F - b.F;
    ll y = a.S - b.S;
    return x *x + y * y;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pll> p(n);
    for(int i =0 ; i < n; i++) cin >> p[i].F >> p[i].S;

    vector<pair<ll, pii>> e;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++) e.eb(mp(dis(p[i], p[j]), mp(i, j)));
    }

    lsort(e);

    dsu.resize(n);
    for(int i = 0; i < n; i++) dsu[i] = i;

    ll ans = 0;
    for(auto i : e){
        if(findDSU(i.S.F) == findDSU(i.S.S)) continue;
        ans = i.F;
        unionDSU(i.S.F, i.S.S);
    }

    cout << fixed << setprecision(20) << sqrt(ans) / 2 << "\n";

    return 0;
}

• Subtask 1: 70 / 70