Submission #336648

#	Time	Username	Problem	Language	Result	Execution time	Memory
336648		neki	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	181 ms	512 KiB

odasiljaci

#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 1010
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007
ll x[mn], y[mn], dsu[mn], siz[mn], cnt, n; 
ll fnd(ll p){return (p==dsu[p]) ? p:fnd(dsu[p]);}
void join(ll a, ll b){
    ll pa=fnd(a), pb=fnd(b);
    if(pa!=pb){
        cnt--;
        if(siz[pa]<siz[pb]) swap(pa, pb);
        dsu[pb]=pa;
        siz[pa]+=siz[pb];
    }
}
ll solve(ll meja){
    loop(i, 1, n+1) dsu[i]=i, siz[i]=1;
    cnt=n;
    loop(i, 1, n+1) loop(j, 1, n+1) if(i!=j and (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j])<=meja) join(i, j);
    return (cnt==1);
}
int main() {
    cin >> n;
    loop(i, 1, n+1) cin >> x[i]>>y[i];
    ll l=0, r=llmax;
    while(l<r){
        ld mid=(l+r)/2;
        if(solve(mid)) r=mid;
        else l=mid+1;
    }
    cout <<setprecision(8)<<fixed<< sqrt(l)/2.0 <<endl;
}

• Subtask 1: 70 / 70