leetcode-go/poj/2560.freckles/main.cc

#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 200;

struct UF {
  int id[N];
  int sz[N];
  int cnt;
} uf;

int find(int i) {
  if (i == uf.id[i]) return i;
  int j = find(uf.id[i]);
  uf.id[i] = j;
  return j;
}

bool is_join(int i, int j) { return find(i) == find(j); }

void join(int i, int j) {
  i = find(i);
  j = find(j);
  if (i == j) return;
  if (uf.sz[i] < uf.sz[j]) {
    uf.id[i] = j;
  } else {
    if (uf.sz[i] == uf.sz[j]) uf.sz[i]++;
    uf.id[j] = i;
  }
  uf.cnt--;
}

struct V {
  double x;
  double y;
  double operator-(const V &that) const {
    double dx = this->x - that.x;
    double dy = this->y - that.y;
    return sqrt(dx * dx + dy * dy);
  }
} v[N];

struct E {
  int v1;
  int v2;
  double len;
  E(int v1, int v2, double len) : v1(v1), v2(v2), len(len) {}
  bool operator<(const E &that) const { return this->len > that.len; }
};

int main() {
  int n, e;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lf %lf", &v[i].x, &v[i].y);
  priority_queue<E> q;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      q.push(E(i, j, v[i] - v[j]));
      e++;
    }
  }
  for (int i = 0; i < n; i++) uf.id[i] = i;
  memset(uf.sz, 0, sizeof(uf.sz));
  uf.cnt = n;
  double len = 0.;
  while (uf.cnt != 1) {
    E edge = q.top();
    q.pop();
    if (is_join(edge.v1, edge.v2)) continue;
    join(edge.v1, edge.v2);
    len += edge.len;
  }
  printf("%.2lf\n", len);
  return 0;
}