思路

最小生成树中最大的边，边权最小

所以这题就变成最小生成树的板子了，跳跃距离大于最大边权的猴子就是可行的

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int x[100000],y[100000],dis[100000],vis[100000],jump[100000],m,n;

struct QNode{

    int x,dis;

    bool operator < (const QNode &b) const{

        return dis>b.dis;

    }

};

priority_queue<QNode> q;

int dist(int a,int b){

    return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);

}

bool prim(void){

    memset(vis,0,sizeof(vis));

    memset(dis,0x3f,sizeof(dis));

    dis[1]=0;

    int cnt=1;

    q.push((QNode){1,0});

    while(!q.empty()&&cnt<n){

        QNode x=q.top();

        q.pop();

        // printf("%d %d\n",x.x,x.dis);

        if(vis[x.x])

            continue;

        vis[x.x]=true;

        cnt++;

        for(int i=1;i<=n;i++)

            if(i!=x.x&&dist(x.x,i)<dis[i]&&!vis[i]){

                dis[i]=dist(x.x,i);

                q.push((QNode){i,dis[i]});

            }

    }

    return cnt==n;

}

int main(){

    scanf("%d",&m);

    for(int i=1;i<=m;i++)

        scanf("%d",&jump[i]);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d %d",&x[i],&y[i]);

    if(!prim()){

        printf("%d\n",0);

        return 0;

    }

    int maxx=0;

    for(int i=1;i<=n;i++)

       maxx=max(dis[i],maxx);

    // printf("max=%d\n",maxx);

    int ans=0;

    for(int i=1;i<=m;i++)

        if(jump[i]*jump[i]>=maxx)

            ans++;

    printf("%d\n",ans);

    return 0;

}