记录编号	575633	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]聪明的猴子	最终得分	100
用户昵称	Lfc_HeSn	是否通过	通过
代码语言	C++	运行时间	2.065 s
提交时间	2022-09-23 22:03:37	内存使用	21.87 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, ans, sum, a[2010], b[1010], c[1010], g[1010][1010], fa[1010], cnt;
struct node {
	int x, y, w;
}e[1000010];
bool cmp(node x, node y) {
	return x.w < y.w;
}
int dist(int x, int y) {
	int w = (b[x] - b[y]) * (b[x] - b[y]) + (c[x] - c[y]) * (c[x] - c[y]);
	return w;
}
int find(int x) {
	if(fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}
void kruskal() {
	for(int i = 1; i <= cnt; i ++) {
		int u = e[i].x, v = e[i].y;
		int a = find(u), b = find(v);
		if(a == b) {
			continue;
		}
		fa[a] = b;
		ans = e[i].w;
	}
}
signed main() {
	freopen("monkey.in", "r", stdin);
	freopen("monkey.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		a[i] *= a[i];
	}
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> b[i] >> c[i];
		fa[i] = i;
	}
	for(int i = 1; i <= m; i ++) {
		for(int j = 1; j <= m; j ++) {
			if(i == j) {
				continue;
			}
			g[i][j] = g[j][i] = dist(i, j);
			e[++ cnt].x = i;
			e[cnt].y = j;
			e[cnt].w = g[i][j];
		}
	}
	sort(e + 1, e + cnt + 1, cmp);
	kruskal();
	for(int i = 1; i <= m; i ++) {
		sum += (a[i] >= ans);
	}
	cout << sum;
    return 0;
}