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