Submission #1318102

#TimeUsernameProblemLanguageResultExecution timeMemory
1318102raminqOdašiljači (COCI20_odasiljaci)C++20
70 / 70
93 ms436 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    
    if (n == 1) {
        cout << "0.0000000000" << endl;
        return 0;
    }
    double left = 0, right = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double dx = x[i] - x[j];
            double dy = y[i] - y[j];
            double dist = sqrt(dx*dx + dy*dy);
            if (dist > right) right = dist;
        }
    }
    for (int iter = 0; iter < 60; iter++) {
        double mid = (left + right) / 2;
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        int count = 1;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    double dx = x[u] - x[v];
                    double dy = y[u] - y[v];
                    double dist = sqrt(dx*dx + dy*dy);
                    if (dist <= 2 * mid) {
                        visited[v] = true;
                        q.push(v);
                        count++;
                    }
                }
            }
        }
        
        if (count == n) {
            right = mid;
        } else {
            left = mid;
        }
    }
    
    cout << fixed << setprecision(10) << right << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...