比赛 EYOI与SBOI开学欢乐赛7th 评测结果 AAAAAAAAAA
题目名称 聪明的猴子 最终得分 100
用户昵称 00000 运行时间 0.891 s
代码语言 C++ 内存使用 17.19 MiB
提交时间 2022-09-23 21:18:04
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,a[2000],n;
struct edge{
	int h,j,k;
}b[2000000];
int bb;
int x[2000],y[2000];
int f[2000];
int cnt,ans=0x3f3f3f3f;
bool cmp(edge f,edge g)
{
	return f.h<g.h;
}
int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
int main(){
	freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout);
cin>>m;
for(int q=1;q<=m;q++)
{
	cin>>a[q];a[q]=a[q]*a[q];
} 
cin>>n;
for(int q=1;q<=n;q++)
{
	cin>>x[q]>>y[q];
	for(int w=1;w<q;w++)
	b[++bb]={(x[q]-x[w])*(x[q]-x[w])+(y[q]-y[w])*(y[q]-y[w]),q,w};
}
for(int q=1;q<=n;q++) f[q]=q;
sort(b+1,b+bb+1,cmp);
for(int q=1;q<=bb;q++)
{
//	cout<<b[q].h<<endl;
	if(cnt==n-1) break;
	int c=find(b[q].j),d=find(b[q].k);
	if(c!=d)
	{
		cnt++;
		ans=b[q].h;
		f[c]=d;
	}
}
int l=0;
for(int q=1;q<=m;q++) if(a[q]>=ans) l++;
cout<<l;
return 0;
}