记录编号	429671	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]聪明的猴子	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.990 s
提交时间	2017-07-27 22:20:42	内存使用	12.01 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=1010;
int n,m;
int hou[maxn];
struct pos{int x,y;}p[maxn];
struct edge{int u,v,w;}e[maxn*maxn];
inline bool cmp(edge a, edge b){return a.w<b.w;}
int fa[maxn];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int juli(pos a,pos b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int tot;
inline int kruskal(){//求最小生成树的最大边 
	int maxx=-0x7fffffff;
	for(int i=1;i<=m;i++)fa[i]=i;
	int cnt=0;
	for(int i=1;i<=tot;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v)fa[u]=v,maxx=e[i].w,cnt++;
		if(cnt==m-1)break;
	}
	return maxx;
}
int main(){
	freopen("monkey.in","r",stdin);
	freopen("monkey.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)hou[i]=read();
	sort(hou+1,hou+n+1);
	m=read();
	for(int i=1;i<=m;i++){
		p[i].x=read();p[i].y=read();
	}
	for(int i=1;i<=m;i++){//建图(稠密);
		for(int j=1;j<=m;j++){
			if(i==j)continue;
			e[++tot].u=i,e[tot].v=j,e[tot].w=juli(p[i],p[j]);
		}
	}
	sort(e+1,e+tot+1,cmp);
	int ok=kruskal();
	int ans=0;
	for(int i=1;i<=n;i++){
		if(hou[i]>=ok){ans=n-i+1;break;}
	}
	printf("%d\n",ans);
	return 0;
}