oj.uz

답안 #875389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875389 2023-11-19T12:53:18 Z HossamHero7 Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 311 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct dsu{
    vector<int> par;
    int comp;
    dsu(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
        comp = n;
    }
    int getP(int node){
        if(node == par[node]) return node;
        return par[node] = getP(par[node]);
    }
    void add(int a,int b){
        a = getP(a) , b = getP(b);
        if(a == b) return;
        par[b] = a;
        comp --;
    }
};
double dis(pair<int,int> p1 , pair<int,int> p2){
    double x1 = p1.first , y1 = p1.second;
    double x2 = p2.first , y2 = p2.second;
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(auto &[x,y] : v) cin>>x>>y;
    double l = 0;
    double r = 1e10;
    double ans = 0;
    for(int _=0;_<200;_++){
        double md = (l + r) / 2;
        dsu ds(n);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(dis(v[i],v[j]) > 2*md) continue;
                ds.add(i,j);
            }
        }
        if(ds.comp == 1) ans = md , r = md;
        else l = md;
    }
    cout<<fixed<<setprecision(6)<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto &[x,y] : v) cin>>x>>y;
      |               ^

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 86 ms 348 KB Output is correct
7 Correct 86 ms 600 KB Output is correct
8 Correct 179 ms 348 KB Output is correct
9 Correct 309 ms 472 KB Output is correct
10 Correct 311 ms 344 KB Output is correct