oj.uz

Submission #401316

# Submission time Handle Problem Language Result Execution time Memory
401316 2021-05-09T20:27:00 Z jenkinsser Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 160 ms 400 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 22 ms 372 KB Output is correct
7 Correct 30 ms 336 KB Output is correct
8 Correct 75 ms 332 KB Output is correct
9 Correct 153 ms 396 KB Output is correct
10 Correct 160 ms 400 KB Output is correct