제출 #1152297

#제출 시각아이디문제언어결과실행 시간메모리
1152297WongYiKaiOdašiljači (COCI20_odasiljaci)C++20
70 / 70
190 ms16784 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n;
    cin >> n;
    vector<pair<ll,ll>> v;
    for (int i=0;i<n;i++){
        ll x,y;
        cin >> x >> y;
        v.push_back({x,y});
    }
    vector<pair<ll,double>> adj[n+5];
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            ll x1=v[i].first, y1 = v[i].second, x2 = v[j].first, y2 = v[j].second;
            double dist = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
            adj[i].push_back({j,dist});
            adj[j].push_back({i,dist});
        }
    }

    ll visited[n+5];
    memset(visited,-1,sizeof(visited));

    ll l=0,r=2000000000000000000;
    while (l<r){
        ll m = l+(r-l)/2;
        visited[0] = m;
        queue<ll> q;
        q.push(0);
        ll count=0;
        while (!q.empty()){
            ll x = q.front();
            q.pop();
            count++;
            for (auto it=adj[x].begin(); it != adj[x].end(); ++it){
                if (visited[(*it).first]==m) continue;
                if ((*it).second > m) continue;
                visited[(*it).first] = m;
                q.push((*it).first);
            }
        }
        if (count < n) l=m+1;
        else r=m;

    }

    cout << fixed << setprecision(15) << sqrt(l)/2;
}
#Verdict Execution timeMemoryGrader output
Fetching results...