제출 #1321157

#제출 시각아이디문제언어결과실행 시간메모리
1321157b_esma101811Odašiljači (COCI20_odasiljaci)C++20
70 / 70
155 ms9096 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e3 + 10;
const double INF = 1e18;
void solve() {
    vector<int> vt;
    int n;
    cin >> n;
    double a[n + 1];
    double b[n + 1];
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    if(n == 1) {
        cout << 0.0000000 << endl;
        return;
    }
    double l = 1, r = 1e9, best = -1, ep = 0.0000001;
    while(r - l >= ep) {
        vector<int> adj[n + 5];
        vector<int> vis(n + 5, 0);
        queue<int> q;
        double m = (l + r) / 2.00;
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                if(sqrt((abs(a[i] - a[j]) / 2) * (abs(a[i] - a[j]) / 2) + (abs(b[i] - b[j]) / 2) * (abs(b[j] - b[i]) / 2)) <= m) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        q.push(1);
        while (q.size()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (int v: adj[u]) {
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
        bool check = true;
        for(int i = 1; i <= n; i++) {
            if(!vis[i]) {
                check = false;
            }
        }
        if(check) {
            r = m;
            best = m;
        }
        else {
            l = m;
        }
    }
    cout << setprecision(7) << fixed << best << endl;
}
signed main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...