Submission #401316

#	Time	Username	Problem	Language	Result	Execution time	Memory
401316		jenkinsser	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	160 ms	400 KiB

odasiljaci

#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 1005;
const int INF = 1e9+5;
const double epsilon = 1e-7;
const int mod = 1e9+7;

struct point{
    int x,y;
};

int n,vis[N];
point points[N];

double calc(point a,point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

void dfs(int v,double r){
    // cout << v << sp << r << nl;
    vis[v]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]&&calc(points[v],points[i])<4.0*r*r){
            dfs(i,r);
        }
    }
}

bool check(){
    for(int i=1;i<=n;i++){
        // cout << vis[i] << sp;
        if(!vis[i])
            return false;
    }
    return true;
}

signed main(){
    fastio()
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> points[i].x >> points[i].y;
    }
    double l=0,r=INF;
    while(r-l>epsilon){
        double m=(l+r)/2;
        // cout << m << nl;
        memset(vis,0,sizeof(vis));
        dfs(1,m);
        if(check())
            r=m;
        else
            l=m;
    }
    cout << setprecision(7) << l << nl;
}

• Subtask 1: 70 / 70