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