找到一道水题真是一件令人开心的事情。
最小生成树。完了。
#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);
}