Submission #334699

#	Time	Username	Problem	Language	Result	Execution time	Memory
334699		lukameladze	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	600 ms	512 KiB

odasiljaci

# include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long p[N];
long double dist;
long double x,le,ri,mid,ans,a[N],b[N],n;
int get_col(int a)
{
     if (p[a]==a) return a;
     return p[a]=get_col(p[a]);
}
void col (int a, int b)
{
     a=get_col(a);
     b=get_col(b);
     p[a]=b;
}
int go(long double r)
{
     for (int i=1; i<=n; i++)
     p[i]=i;
     for (int i=1; i<=n; i++)
     {
          for (int j=i+1; j<=n; j++)
          {
               dist=sqrt(abs(a[i]-a[j])*abs(a[i]-a[j])+abs(b[i]-b[j])*abs(b[i]-b[j]));
               //cout<<i<<" "<<j<<" "<<dist<<" "<<r<<endl;
               if (dist<=2*r) col(i,j);
          }
     }
     //cout<<"gam"<<endl;
     for (int i=2; i<=n; i++)
     {
         // cout<<get_col(i)<<" "<<get_col(i-1)<<endl;
          if (get_col(i)!=get_col(i-1)) return 0;
     }
     return 1;
}
int main()
{
     	cout<<setprecision(9)<<fixed; 
     cin>>n;
     for (int i=1; i<=n; i++)
     {
          cin>>a[i]>>b[i];
     }
     le=0;
     ri=1e9;
     x=1e-9;
     while (le<=ri-x)
     {
          //cout<<mid<<endl;
          mid=(le+ri)/2;
          if (go(mid)==1)
          {
                ans=mid;
               ri=mid-x;
          }
          else le=mid+x;
     }
     cout<<ans<<endl;
}

• Subtask 1: 70 / 70