题目名称	1310. [HAOI 2006]聪明的猴子
输入输出	`monkey.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2013-03-10加入
开放分组	全部用户
提交状态
分类标签	最小生成树 HAOI 并查集
	分享题解

通过：139，提交：444，通过率：31.31%
xxcxcxcx	100	0.013 s	0.17 MiB	C++
LGLJ	100	0.045 s	2.45 MiB	C++
xxcxcxcx	100	0.048 s	0.33 MiB	C++
会不才蛋笨	100	0.049 s	0.33 MiB	C++
ty_c7x1	100	0.049 s	3.76 MiB	C++
Gilgamesh	100	0.055 s	0.28 MiB	C++
yushi	100	0.058 s	4.15 MiB	C++
HouJikan	100	0.061 s	0.33 MiB	C++
Narcissus	100	0.062 s	0.31 MiB	C++
yun	100	0.065 s	4.15 MiB	C++

本题关联比赛
EYOI与SBOI开学欢乐赛7th

关于聪明的猴子的近10条评论(全部评论)
难受了，比赛结束后一分钟写出来了（ Lfc_HeSn 2022-09-23 22:02 10楼
Richard 2019-07-04 09:55 9楼
数组永远开小系列…… Shirry 2017-10-04 16:26 8楼
内存限制充裕情况下，多开空间总比少开要好（因为我数组开小E了）。 Fisher. 2017-07-27 22:21 7楼
把猴子数当成了边数。。智商捉急ing。。。。一個人的雨 2015-04-12 16:37 6楼
mark Ezio 2014-09-23 14:56 5楼
莫非prim不能用堆优化吗？？o(n^2)的prim就对，克鲁斯卡尔也对，就是堆优化prim错了TAT HouJikan 2014-09-23 11:35 4楼
怎么得到相邻两棵树的最大距离呢。。。。求指教。。 Letter zZZz 2014-04-19 22:10 3楼
数据已修改苏轼 2013-03-29 13:18 2楼
数据对不对啊...第一个数据求解释 CAX_CPG 2013-03-12 09:08 1楼

1310. [HAOI 2006]聪明的猴子

★☆ 输入文件：monkey.in 输出文件：monkey.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的部分植物的树冠上来回穿梭，以找到喜欢吃的果实。

现在，在这个地区露出水面的有 $N$ 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示（任意两棵树的坐标都不相同）。

在这个地区住着的猴子有 $M$ 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远（当然也可以跳到较近的树上），而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。

任务：现已知猴子的数量及每一个猴子的最大跳跃的距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少猴子可以在这个地区露出水面的所有树冠上觅食。

【输入格式】

第一行一个整数，表示猴子的个数 $M$;

第二行为 $M$ 个整数，依次表示猴子的最大跳跃距离（距离范围：$[1,1000]$）;

第三行为一个整数，表示树的总棵树 $N$;

第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标（坐标均为整数，范围：$[-1000,1000]$）;

【输出格式】

输出只有一行，包括一个整数，表示可以有这个地区的所有树冠上觅食的猴子数。

【样例输入1】

【样例输出1】

【样例输入输出2】

样例2

【提示】

对于 $40\%$ 的数据，保证有 $2 \leq N \leq 100,1 \leq M \leq 100$;

对于 $100\%$ 的数据，保证有 $2 \leq N \leq 1000,1 \leq M \leq 500$;