记录编号	576466	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]聪明的猴子	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.311 s
提交时间	2022-10-10 09:08:54	内存使用	12.75 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,q=0,cnt=0;
int jump[510],f[1010],d[1010][1010];
struct point{
    int x,y;
}h[1001];
struct edge{
    int start,end,width;
}g[1001000];
int cmd(edge a,edge b){
	return a.width<b.width;
}
int find(int start){
	if(f[start]==start||f[start]==0){
		return f[start]=start;
	}
	else{
		return f[start]=find(f[start]);
	}
}
int kruskal(){
    int cnt=0;
    for(int i=1;i<=q;i++){
        int x=find(g[i].start);
        int y=find(g[i].end);
        if(x!=y){
            f[x]=y;
            if(++cnt>=m-1){
            	return g[i].width;
            }
        }
    }
}
int main(){
	freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>jump[i];
        jump[i]=jump[i]*jump[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>h[i].x>>h[i].y;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(i>=j){
            	continue;
            }
            int u=(h[i].x-h[j].x)*(h[i].x-h[j].x)+(h[i].y-h[j].y)*(h[i].y-h[j].y);
            if(u!=0){
            	g[++q]=(edge){i,j,u};
            }
        }
    }
    sort(g+1,g+1+q,cmd);
    int p=kruskal();
    for(int i=1;i<=n;i++){
        if(jump[i]>=p){
        	cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}