oj.uz

Submission #334699

# Submission time Handle Problem Language Result Execution time Memory
334699 2020-12-09T19:48:25 Z lukameladze Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 600 ms 512 KB 
# 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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 6 ms 364 KB Output is correct
6 Correct 177 ms 364 KB Output is correct
7 Correct 174 ms 492 KB Output is correct
8 Correct 388 ms 364 KB Output is correct
9 Correct 600 ms 364 KB Output is correct
10 Correct 523 ms 512 KB Output is correct