记录编号	158079	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]聪明的猴子	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.685 s
提交时间	2015-04-12 16:35:15	内存使用	15.05 MiB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge{
	int qs,zz,w;
}E[1000010];
int n,m,sum=0,f[1000010],cnt=0,ans=0,k=0;
int a[100000],x[100000],y[100000];

int find(int x) 
{ 
     return x==f[x]?x:f[x]=find(f[x]);  
}
  
void uinon(int x,int y)  
{  
    int p=find(x),q=find(y);  
    if(p!=q)  
    {  
        f[p]=q;   
    }  
} 

int cmp(const Edge &x,const Edge &y){
	return x.w<y.w;
} 

int main()
{
	freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;++i)
	 scanf("%d",&a[i]);
	cin>>m;
	for (int i=1;i<=m;++i)
	 scanf("%d%d",&x[i],&y[i]);
	for (int i=1;i<=m;++i)
	 for (int j=1;j<=m;++j)
	  if (i!=j)
	   {
	   	sum++;
	   	E[sum].qs=i;
	   	E[sum].zz=j;
	   	E[sum].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	   }
	for (int i=1;i<=sum;++i)
	 f[i]=i;
	sort(E+1,E+sum+1,cmp);
    for (int i=1;i<=sum;++i)
    {
 	 if (find(E[i].qs)!=find(E[i].zz))
 	 {
 		uinon(E[i].qs,E[i].zz);
 		if (E[i].w>ans)
 		 ans=E[i].w;
 		k++;
 	 }
 	 if (k==m-1) 
 	 {
 		break;
 	 }
    }
    for (int i=1;i<=n;++i)
     if (a[i]>=ans) cnt++;
    cout<<cnt;
    return 0;
}