比赛 |
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;
}