leetcode-go/poj/2349.arctic-network/main.cc

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

using namespace std;

const int S = 100;
const int P = 500;

struct V {
  int x;
  int y;
  V(int x = 0, int y = 0) : x(x), y(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);
  }
} outpost[P];

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

struct UF {
  int id[P];
  int sz[P];
  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;
}

void unite(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--;
}

int main() {
  int n, s, p, k;
  scanf("%d", &n);
  while (n--) {
    scanf("%d %d", &s, &p);
    for (int i = 0; i < p; i++) {
      scanf("%d %d", &outpost[i].x, &outpost[i].y);
      uf.id[i] = i;
    }
    memset(uf.sz, 0, sizeof(uf.sz));
    uf.cnt = p, k = 0;
    priority_queue<E> pq;
    for (int i = 0; i < p - 1; i++)
      for (int j = i + 1; j < p; j++) pq.push(E(i, j, outpost[i] - outpost[j]));
    double d = 0.;
    while (1 < uf.cnt) {
      E e = pq.top(); // No const E & !!! WA * 4
      pq.pop();
      if (find(e.u) == find(e.v)) continue;
      unite(e.u, e.v);
      if (++k == p - s) {
        d = e.len;
        break;
      }
    }
    printf("%.2f\n", d);
  }
  return 0;
}