比赛 EYOI与SBOI开学欢乐赛7th 评测结果 AAAAAAAAAA
题目名称 聪明的猴子 最终得分 100
用户昵称 ZRQ 运行时间 0.934 s
代码语言 C++ 内存使用 12.60 MiB
提交时间 2022-09-23 20:45:42
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct edge
{
	int u,v,w;
}e[N];
int n,m,fa[N],x[1005],y[1005],a[505],idx,mx,cnt,ans,sig;
char ch;
inline void read(int &x){sig=1;x=0;ch=getchar();while(ch<48||ch>57){if(ch==45)sig=-1;ch=getchar();}while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x*=sig;return ;}
int dist(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline bool cmp1(edge a,edge b){return a.w<b.w;}
int main()
{
	freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout); 
	read(m);
	for(int i=1;i<=m;++i) read(a[i]);
	read(n);
	for(int i=1;i<=n;++i) read(x[i]),read(y[i]),fa[i]=i;
	for(int i=2;i<=n;++i)
		for(int j=1;j<i;++j)
			e[++idx]=(edge){j,i,dist(i,j)};
	sort(e+1,e+idx+1,cmp1);
	for(int i=1;i<=idx;++i)
	{
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx!=fy)
		{
			fa[fy]=fx;
			mx=e[i].w;
			++cnt;
		}
		if(cnt==n-1) break;
	}
	for(int i=1;i<=m;++i) if(a[i]*a[i]>=mx) ++ans;
	printf("%d",ans);
	return 0;
}