比赛 EYOI与SBOI开学欢乐赛7th 评测结果 AAAAAAAAAA
题目名称 聪明的猴子 最终得分 100
用户昵称 lihaoze 运行时间 0.903 s
代码语言 C++ 内存使用 10.45 MiB
提交时间 2022-09-23 21:22:04
显示代码纯文本
#include <bits/stdc++.h>

using PII = std::pair<int, int>;

struct E { int a, b, w; };

const int N = 1010;
int n, m, idx, cnt, res, ans;
int a[N], p[N];
PII d[N];
E edge[N * N];

int dist(PII a, PII b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

void merge(int a, int b) {
	int x = find(a), y = find(b);
	if (x != y) p[x] = y;
}

int main() {
	freopen("monkey.in", "r", stdin);
	freopen("monkey.out", "w", stdout);
	for (int i = 1; i < N; ++ i) p[i] = i;
	std::cin >> n;
	for (int i = 1; i <= n; ++ i)
		std::cin >> a[i];
	std::cin >> m;
	for (int i = 1; i <= m; ++ i) {
		auto& [x, y] = d[i];
		std::cin >> x >> y;
	}
	for (int i = 1; i <= m; ++ i)
		for (int j = 1; j < i; ++ j)
			edge[++ idx] = { i, j, dist(d[i], d[j]) };
	std::sort(edge + 1, edge + 1 + idx, [](E a, E b) { return a.w < b.w; });
	for (int i = 1; i <= idx; ++ i) {
		auto [a, b, w] = edge[i];
		if (find(a) != find(b)) 
			merge(a, b), res = w;
	}
	for (int i = 1; i <= n; ++ i)
		ans += a[i] * a[i] >= res;
	std::cout << ans << '\n';
	return 0;
}