fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double lb;
  5. const int MAXN = 1e3 + 7;
  6. pair <ll, ll> save[MAXN];
  7. lb ans = 0;
  8. int n;
  9. struct edges{
  10.     int x, y;
  11.     lb w;
  12. };
  13. vector <edges> edge;
  14.  
  15. struct DSU{
  16.   int par[MAXN];
  17.   DSU(){fill(par + 1, par + 1 + n, -1);}
  18.   int find(int u){return par[u] < 0 ? u : par[u] = find(par[u]);}
  19.   bool join(int x, int y){
  20.     x = find(x);
  21.     y = find(y);
  22.     if(x == y) return false;
  23.     if(par[x] > par[y]) swap(x, y);
  24.     par[x] += par[y];
  25.     par[y] = x;
  26.     return true;
  27.   }
  28. };
  29.  
  30.  
  31. int main(){
  32.     ios_base::sync_with_stdio(0);
  33.     cout.tie(0);
  34.     cin.tie(0);
  35.     cout << fixed << setprecision(6);
  36.     cin >> n;
  37.     DSU dsu;
  38.     for(int i = 1; i <= n; i++){
  39.         int x, y;
  40.         cin >> x >> y;
  41.         save[i] = {x, y};
  42.     }
  43.  
  44.     for(int i = 1; i < n; i++){
  45.         for(int j = i + 1; j <= n; j++){
  46.             lb a = abs(save[i].first - save[j].first);
  47.             lb b = abs(save[i].second - save[j].second);
  48.             lb dist = sqrt(a * a + b * b);
  49.             edge.push_back({i, j, dist});
  50.         }
  51.     }
  52.     sort(edge.begin(), edge.end(), [&] (edges a, edges b){
  53.         return a.w < b.w;
  54.     });
  55.     for(auto i : edge){
  56.         int x = i.x;
  57.         int y = i.y;
  58.         lb w = i.w;
  59.         if(dsu.join(x, y))ans = max(ans, w);
  60.     }
  61.     cout << ans / 2;
  62. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/awSw98
language:
C++14 (gcc 8.3)
created:
10 days 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!