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