laekov

找到一道水题真是一件令人开心的事情。

最小生成树。完了。

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

#define sqr(x) ((x)*(x))

struct edge {

int a, b, v;

edge(int a0 = 0, int b0 = 0, int v0 = 0) {

a = a0, b = b0, v = v0;

}

};

const int maxn = 1009;

int n, m, a[maxn], t, x[maxn], y[maxn], r[maxn];

edge e[maxn * maxn];

inline bool cmpE(const edge& a, const edge& b) {

return a. v < b. v;

}

inline int getRoot(int x) {

return (r[x] == x) ? x : (r[x] = getRoot(r[x]));

}

int kruskal() {

int s = 0;

sort(e, e + t, cmpE);

for (int i = 1; i <= n; ++ i)

r[i] = i;

for (int i = 0; i < t; ++ i)

if (getRoot(e[i]. a) ^ getRoot(e[i]. b)) {

s = e[i]. v;

r[getRoot(e[i]. a)] = getRoot(e[i]. b);

}

return s;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d", &m);

for (int i = 0; i < m; ++ i)

scanf("%d", a + i);

scanf("%d", &n);

t = 0;

for (int i = 0; i < n; ++ i) {

scanf("%d%d", x + i, y + i);

for (int j = 0; j < i; ++ j)

e[t ++] = edge(i, j, sqr(x[i] - x[j]) + sqr(y[i] - y[j]));

}

int v = kruskal(), s = 0;

for (int i = 0; i < m; ++ i)

if (sqr(a[i]) >= v)

++ s;

printf("%d\n", s);

}