fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e3 + 5;
  5.  
  6. long long n;
  7. pair<long long,long long> pr[MaxN];
  8.  
  9. vector<long long> arr[MaxN];
  10. bool visited[MaxN];
  11.  
  12. void bfs(long long x, vector<long long> arr[], bool visited[])
  13. {
  14.     queue<long long> q;
  15.  
  16.     q.push(x);
  17.     visited[x]=true;
  18.  
  19.     while(!q.empty())
  20.     {
  21.         long long u=q.front();
  22.         q.pop();
  23.  
  24.         for(long long v:arr[u])
  25.         {
  26.             if(!visited[v])
  27.             {
  28.                 visited[v]=true;
  29.                 q.push(v);
  30.             }
  31.         }
  32.     }
  33. }
  34.  
  35. bool check(long double R)
  36. {
  37.     for(long long i=1;i<=n;i++)
  38.     {
  39.         arr[i].clear();
  40.         visited[i]=false;
  41.     }
  42.  
  43.     for(long long i=1;i<=n;i++)
  44.     {
  45.         for(long long j=i+1;j<=n;j++)
  46.         {
  47.             long long dx=pr[i].first-pr[j].first;
  48.             long long dy=pr[i].second-pr[j].second;
  49.  
  50.             long long dis2=dx*dx+dy*dy;
  51.  
  52.             if((long double)dis2 <= 4*R*R)
  53.             {
  54.                 arr[i].push_back(j);
  55.                 arr[j].push_back(i);
  56.             }
  57.         }
  58.     }
  59.  
  60.     bfs(1,arr,visited);
  61.  
  62.     for(long long i=1;i<=n;i++)
  63.     {
  64.         if(!visited[i])
  65.         {
  66.             return false;
  67.         }
  68.     }
  69.  
  70.     return true;
  71. }
  72.  
  73. void input()
  74. {
  75.     cin>>n;
  76.  
  77.     for(long long i=1;i<=n;i++)
  78.     {
  79.         cin>>pr[i].first>>pr[i].second;
  80.     }
  81. }
  82.  
  83. void solve()
  84. {
  85.     double l=0;
  86.     double r=1e9+5;
  87.  
  88.     for(long long it=1;it<=60;it++)
  89.     {
  90.         double mid=(l+r)/2;
  91.  
  92.         if(check(mid))
  93.         {
  94.             r=mid;
  95.         }
  96.         else
  97.         {
  98.             l=mid;
  99.         }
  100.     }
  101.  
  102.     cout<<fixed<<setprecision(6)<<r;
  103. }
  104. int main()
  105. {
  106.     ios_base::sync_with_stdio(0);
  107.     cin.tie(0);
  108.  
  109.     input();
  110.     solve();
  111. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/3tbQyJ
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!