fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ll long long
  5. using namespace std;
  6. const int MAXN = 1010;
  7. pair<int, int> c[MAXN];
  8. vector<pair<int, pair<int, int>>> edge;
  9. int n;
  10. struct DSU{
  11.     int parent[MAXN];
  12.     DSU(){
  13.         for (int i = 1; i <= n; i++){
  14.              parent[i] = i;
  15.         }
  16.     }
  17.     int find(int u){
  18.         if (parent[u] != u) return parent[u] = find(parent[u]);
  19.         return parent[u];
  20.     }
  21.     bool unite(int u, int v){
  22.         u = find(u);
  23.         v = find(v);
  24.         if (u == v) return false;
  25.         parent[u] = v;
  26.         return true;
  27.     }
  28. };
  29. int dist(pair<int, int> &a, pair<int, int> &b){
  30.     return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
  31. }
  32. int main(){
  33.     freopen("moocast.in", "r", stdin);
  34.     freopen("moocast.out", "w", stdout);
  35.     ios_base::sync_with_stdio(0);
  36.     cin.tie(0);
  37.     cin >> n;
  38.     for (int i = 1; i <= n; i++){
  39.          cin >> c[i].first >> c[i].second;
  40.     }
  41.     for (int i = 1; i <= n; i++){
  42.          for (int j = i + 1; j <= n; j++){
  43.               edge.push_back({dist(c[i], c[j]), {i, j}});
  44.          }
  45.     }
  46.     sort(edge.begin(), edge.end());
  47.     DSU s;
  48.     int cnt = 0;
  49.     int ans = 0;
  50.     for (auto e: edge){
  51.         int w = e.fi;
  52.         int u = e.se.fi;
  53.         int v = e.se.se;
  54.         if (s.unite(u, v)){
  55.             ans = max(ans, w);
  56.             cnt++;
  57.         }
  58.         if (cnt == n - 1){
  59.             break;
  60.         }
  61.     }
  62.     cout << ans << '\n';
  63. }
  64.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Fl4BR9
language:
C++14 (gcc 8.3)
created:
4 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!