fork download 
  1. #include <bits/stdc++.h>
  2. #define el "\n"
  3. #define int long long
  4. #define mp make_pair
  5. #define lb lower_bound
  6. #define ub upper_bound
  7. #define fi first
  8. #define se second
  9. #define sz(x) ((int)(x).size())
  10. #define all(v) (v).begin(), (v).end()
  11. #define pb push_back
  12. #define prs(n) fixed << setprecision(n)
  13.  
  14. const int mod = 1e9 + 7;
  15. const int N = 1e5 + 5;
  16.  
  17. inline int gcd(int a, int b) {
  18.   if (b == 0) return a;
  19.   return gcd(b, a % b);
  20. }
  21. inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
  22.  
  23. using namespace std;
  24.  
  25. int n;
  26. int par[N];
  27. pair<int, int> a[N];
  28.  
  29. int find (int u) {
  30.   if (u == par[u]) return u;
  31.   return par[u] = find(par[u]);
  32. }
  33.  
  34. bool join (int u, int v) {
  35.   u = find(u);
  36.   v = find(v);
  37.   if (u == v) return false;
  38.   par[u] = v;
  39.   return true;
  40. }
  41.  
  42. int dist (int i, int j) {
  43.   int dx = a[i].fi - a[j].fi;
  44.   int dy = a[i].se - a[j].se;
  45.   return dx * dx + dy * dy;
  46. }
  47.  
  48. bool cmpX (tuple<int, int, int> a, tuple<int, int, int> b) {
  49.   return get<0>(a) < get<0>(b);  
  50. }
  51.  
  52. bool cmpY (tuple<int, int, int> a, tuple<int, int, int> b) {
  53.   return get<1>(a) < get<1>(b);  
  54. }
  55.  
  56. signed main() {
  57.   ios_base::sync_with_stdio(false);
  58.   cin.tie(0);
  59.   cout.tie(0);
  60.  
  61. #ifndef ONLINE_JUDGE
  62.   freopen("test.inp", "r", stdin);
  63.   freopen("test.out", "w", stdout);
  64. #endif
  65.  
  66.   cin >> n;
  67.   for (int i = 0; i < n; i++) {
  68.     cin >> a[i].fi >> a[i].se;
  69.     par[i] = i;
  70.   }
  71.  
  72.   // vector<tuple<int, int, int>> points;
  73.   // for (int i = 0; i < n; i++)
  74.   //   points.pb({a[i].fi, a[i].se, i});
  75.  
  76.   vector<tuple<int, int, int>> edges;
  77.   // sort(all(points), cmpX);
  78.   // for (int i = 1; i < n; i++) {
  79.   //   int u = get<2>(points[i - 1]);
  80.   //   int v = get<2>(points[i]);
  81.   //   edges.pb({dist(u, v), u, v});
  82.   // }
  83.  
  84.   // sort(all(points), cmpY);
  85.   // for (int i = 1; i < n; i++) {
  86.   //   int u = get<2>(points[i - 1]);
  87.   //   int v = get<2>(points[i]);
  88.   //   edges.pb({dist(u, v), u, v});
  89.   // }
  90.  
  91.   for (int type = 0; type < 4; ++type) {
  92.     vector<tuple<int,int,int>> points;
  93.     for (int i = 0; i < n; i++) {
  94.       int f;
  95.       if (type == 0) f = a[i].fi; // x
  96.       if (type == 1) f = a[i].se; // y
  97.       if (type == 2) f = a[i].fi + a[i].se; // x + y
  98.       if (type == 3) f = a[i].fi - a[i].se; // x - y
  99.       points.pb({f, i, 0}); 
  100.     }
  101.     sort(all(points));
  102.     for (int i = 1; i < n; i++) {
  103.       int u = get<1>(points[i - 1]);
  104.       int v = get<1>(points[i]);
  105.       edges.pb({dist(u, v), u, v});
  106.     }
  107.   }
  108.  
  109.   sort(all(edges));
  110.   int res = 0, nodes = 0;
  111.   for (auto [w, u, v] : edges) {
  112.     if (join(u, v)) {
  113.       res += w;
  114.       nodes++;
  115.       if (nodes == n - 1) break;
  116.     }
  117.   }
  118.  
  119.   cout << res << el;
  120.  
  121.   return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
0 0
0 10
10 10
5 10
8 8
stdout 
146
https://ideone.com/lKXlUK
language:
C++14 (gcc 8.3)
created:
9 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!