fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const int MAX_Y = 10;
  6.  
  7. //-------------------- DSU --------------------
  8. struct DSU {
  9.     vector<int> parent, sizes;
  10.  
  11.     DSU(int n) {
  12.         parent.resize(n);
  13.         sizes.assign(n, 1);
  14.         for (int i = 0; i < n; i++) parent[i] = i;
  15.     }
  16.  
  17.     int find(int a) {
  18.         if (parent[a] == a) return a;
  19.         return parent[a] = find(parent[a]);
  20.     }
  21.  
  22.     bool unite(int a, int b) {
  23.         a = find(a);
  24.         b = find(b);
  25.         if (a == b) return false;
  26.         if (sizes[b] > sizes[a]) swap(a, b);
  27.         parent[b] = a;
  28.         sizes[a] += sizes[b];
  29.         return true;
  30.     }
  31. };
  32.  
  33. //-------------------- Structs --------------------
  34. struct Point {
  35.     ll x, y;
  36.     int idx;
  37. };
  38.  
  39. struct Edge {
  40.     ll dist;
  41.     int u, v;
  42.     bool operator<(const Edge &other) const {
  43.         return dist < other.dist;
  44.     }
  45. };
  46.  
  47. //-------------------- Main --------------------
  48. int main() {
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.  
  52.     int n;
  53.     cin >> n;
  54.  
  55.     vector<Point> points(n);
  56.     for (int i = 0; i < n; i++) {
  57.         cin >> points[i].x >> points[i].y;
  58.         points[i].idx = i;
  59.     }
  60.  
  61.     // sắp xếp theo x trước, rồi y
  62.     sort(points.begin(), points.end(), [](const Point &a, const Point &b) {
  63.         if (a.x == b.x) return a.y < b.y;
  64.         return a.x < b.x;
  65.     });
  66.  
  67.     // buffer lưu điểm có x lớn nhất cho mỗi y
  68.     vector<Point> buffer(MAX_Y + 1, {-1, -1, -1});
  69.     vector<Edge> edges;
  70.  
  71.     for (int i = 0; i < n; i++) {
  72.         for (int y = 0; y <= MAX_Y; y++) {
  73.             if (buffer[y].idx != -1) {
  74.                 ll dx = points[i].x - buffer[y].x;
  75.                 ll dy = points[i].y - buffer[y].y;
  76.                 ll dist = dx * dx + dy * dy;
  77.                 edges.push_back({dist, points[i].idx, buffer[y].idx});
  78.             }
  79.         }
  80.         buffer[points[i].y] = points[i];
  81.     }
  82.  
  83.     sort(edges.begin(), edges.end());
  84.  
  85.     // Kruskal MST
  86.     DSU dsu(n);
  87.     ll ans = 0;
  88.     for (auto &e : edges) {
  89.         if (dsu.unite(e.u, e.v)) ans += e.dist;
  90.     }
  91.  
  92.     cout << ans << "\n";
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
stdout
copy 
660
https://ideone.com/kQ2ZT4
language:
C++14 (gcc 8.3)
created:
8 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!