debug2

HHLGsmrdfq · 2025-05-10 16:46:09 · 个人记录

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,w;
}e[500001];
int maxd=-1,m,n,x,y,l,ans;
int fa[1001],d[1001];
int tx[1001],ty[1001];
int findfa(int now){
    if(fa[now]==now){
        return now;
    }
    return fa[now]=findfa(fa[now]);
}
bool cmp(Edge &a,Edge &b){
    return a.w<b.w;
}
void Kruskal(int s){
    sort(e+1,e+s+1,cmp);
    int note=0;
    for(int i=1;i<=s;i++){
        int x=findfa(e[i].u),y=findfa(e[i].v);
        if(x!=y){
            fa[x]=y;
            maxd=max(maxd,e[i].w);
            ++note;
            if(note==n-1){
                break;
            }
        }
    }
}
int main(){
    cin>>m;
    for(int i=1;i<=m;++i){
        cin>>d[i];
    }
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x>>y;
        tx[i]=x,ty[i]=y;
    } 
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            ++l;
            e[l].u=i,e[l].v=j,e[l].w=pow(tx[i]-tx[j],2)+pow(ty[i]-ty[j],2);
        }
    }
    Kruskal(l);
    for(int i=1;i<=m;++i){
        if(pow(d[i],2)>=maxd){
            ++ans;
        }
    }
    cout<<ans;
    return 0;
}