제출 #1334156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1334156		ahmetlbktd4	Odašiljači (COCI20_odasiljaci)	C++20	42 / 70	35 ms	516 KiB

odasiljaci

#include "bits/stdc++.h"
#define ll long long
#define ff first
#define ss second
using namespace std;

const int N = 1e3+3;
const double eps = 1e-7;

int n,k;
pair<int,int> a[N];
bool v[N];

void dfs(int nd,double r){
    k++;
    v[nd] = 1;
    for (int i = 0;i < n;i++){
        if (i^nd && !v[i] && (ll)((a[nd].ff-a[i].ff)*(a[nd].ff-a[i].ff) + (a[nd].ss-a[i].ss)*(a[nd].ss-a[i].ss)) < (ll)4*r*r)
        dfs(i,r);
    }
}

bool ok(double r){
    memset(v,0,sizeof(v));
    k = 0;
    dfs(0,r);
    return k==n;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++){
        cin >> a[i].ff >> a[i].ss; 
    }
    double l = 0,r = 1e9;
    while (r-l > eps){
        double md = (l+r)/2;
        if (ok(md))
        r = md;
        else l = md;
    }
    cout.precision(7);
    cout << fixed << l << "\n";
}

• Subtask 1: 42 / 70