题目名称 1310. [HAOI 2006]聪明的猴子
输入输出 monkey.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2013-03-10加入
开放分组 全部用户
提交状态
分类标签
最小生成树 HAOI 并查集
分享题解
通过:139, 提交:444, 通过率:31.31%
Gravatarxxcxcxcx 100 0.013 s 0.17 MiB C++
GravatarLGLJ 100 0.045 s 2.45 MiB C++
Gravatarxxcxcxcx 100 0.048 s 0.33 MiB C++
Gravatar会不才蛋笨 100 0.049 s 0.33 MiB C++
Gravatarty_c7x1 100 0.049 s 3.76 MiB C++
GravatarGilgamesh 100 0.055 s 0.28 MiB C++
Gravataryushi 100 0.058 s 4.15 MiB C++
GravatarHouJikan 100 0.061 s 0.33 MiB C++
GravatarNarcissus 100 0.062 s 0.31 MiB C++
Gravataryun 100 0.065 s 4.15 MiB C++
本题关联比赛
EYOI与SBOI开学欢乐赛7th
关于 聪明的猴子 的近10条评论(全部评论)
难受了,比赛结束后一分钟写出来了(
GravatarHeSn
2022-09-23 22:02 10楼
GravatarRichard
2019-07-04 09:55 9楼
数组永远开小系列……
GravatarShirry
2017-10-04 16:26 8楼
内存限制充裕情况下,多开空间总比少开要好(因为我数组开小E了)。
GravatarFisher.
2017-07-27 22:21 7楼
把猴子数当成了边数。。智商捉急ing。。。。
Gravatar一個人的雨
2015-04-12 16:37 6楼
mark
GravatarEzio
2014-09-23 14:56 5楼
莫非prim不能用堆优化吗??o(n^2)的prim就对,克鲁斯卡尔也对,就是堆优化prim错了TAT
GravatarHouJikan
2014-09-23 11:35 4楼
怎么得到相邻两棵树的最大距离呢。。。。求指教。。
GravatarLetter zZZz
2014-04-19 22:10 3楼
数据已修改
Gravatar苏轼
2013-03-29 13:18 2楼
数据对不对啊...第一个数据求解释
GravatarCAX_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】

4
1 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2

【样例输出1】

3

【样例输入输出2】

样例2

【提示】

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

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