比赛 |
EYOI与SBOI开学欢乐赛7th |
评测结果 |
AWWAWWWWWA |
题目名称 |
聪明的猴子 |
最终得分 |
30 |
用户昵称 |
HeSn |
运行时间 |
0.877 s |
代码语言 |
C++ |
内存使用 |
8.13 MiB |
提交时间 |
2022-09-23 21:06:45 |
显示代码纯文本
#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], vis[1010];
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;
}
bool dfs(int x, int s) {
int f = 1;
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= m; j ++) {
if(vis[i] && g[i][j] <= s) {
vis[j] = 1;
}
if(vis[j] && g[i][j] <= s) {
vis[i] = 1;
}
}
}
for(int i = 1; i <= m; i ++) {
if(!vis[i]) {
return 0;
}
}
return f;
}
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];
}
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= m; j ++) {
g[i][j] = g[j][i] = dist(i, j);
}
}
int l = 1, r = 1000000001;
while(l < r) {
memset(vis, 0, sizeof(vis));
int mid = (l + r) >> 1;
vis[1] = 1;
if(dfs(1, mid)) {
ans = mid;
r = mid;
}
else {
l = mid + 1;
}
}
for(int i = 1; i <= m; i ++) {
sum += (a[i] >= ans);
}
cout << sum;
return 0;
}