Submission #792342

#	Time	Username	Problem	Language	Result	Execution time	Memory
792342		1075508020060209tc	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	263 ms	356 KiB

odasiljaci

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
//#pragma GCC target("popcnt")
using namespace std;
#define int long long
int n;
int ar[500005];
int br[500005];
int uf[500005];

int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}

double dst(int i,int j){
int a=ar[i]-ar[j];int b=br[i]-br[j];
return sqrt(a*a+b*b);
}


int ok(double mi){
for(int i=1;i<=n;i++){
    uf[i]=i;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(dst(i,j)<mi+mi){
            mrg(i,j);
        }
    }
}
for(int i=1;i<=n;i++){
    if(fin(i)!=fin(1)){return 0;}
}
return 1;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i]>>br[i];
    }
    double l=0;double r=1000000000;
    for(int i=1;i<=80;i++){
        double mi=(l+r)/2;
        if(ok(mi)){
            r=mi;
        }else{
            l=mi;
        }
    }
    cout<<fixed<<setprecision(7)<<l;
}

• Subtask 1: 70 / 70