oj.uz

Submission #336648

# Submission time Handle Problem Language Result Execution time Memory
336648 2020-12-16T08:22:06 Z neki Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 181 ms 512 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 64 ms 364 KB Output is correct
7 Correct 63 ms 512 KB Output is correct
8 Correct 138 ms 364 KB Output is correct
9 Correct 181 ms 364 KB Output is correct
10 Correct 122 ms 364 KB Output is correct