Submission #1152259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152259		hmm789	Odašiljači (COCI20_odasiljaci)	C++20	35 / 70	86 ms	8592 KiB

odasiljaci

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define INF 1000000000000000000
#define MOD 1000000007

vector<int> adj[1000];
bool v[1000];
void dfs(int x) {
    v[x] = 1;
    for(int i : adj[x]) if(!v[i]) dfs(i);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int x[n], y[n];
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    double l = 0, r = 1e9, m;
    while(r-l > 1e-7) {
        m = (l+r)/2;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= m*m*4) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        dfs(0);
        bool f = true;
        for(int i = 0; i < n; i++) if(!v[i]) f = false;
        if(f) r = m;
        else l = m;
        for(int i = 0; i < n; i++) {
            adj[i].clear();
            v[i] = 0;
        }
    }
    cout << l << '\n';
}

• Subtask 1: 35 / 70