申请添加 LaTeX
查看原帖
申请添加 LaTeX
963247
Slient_QwQ楼主2023/9/4 12:59
# [HAOI2006] 聪明的猴子

## 题目描述

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

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

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

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

## 输入格式

输入文件`monkey.in`包括:

第 $1$ 行为一个整数,表示猴子的个数 $M$ $(2 <= M <= 500)$;

第 $2$ 行为 $M$ 个整数,依次表示猴子的最大跳跃距离(每个整数值在 $1 \sim 1000$ 之间);

第 $3$ 行为一个整数表示树的总棵数 $N$ $(2 <= N <= 1000)$ ;

第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标(横纵坐标均为整数,范围为:$-1000 \sim 1000$)。

(同一行的整数间用空格分开)

## 输出格式

输出文件 `monkey.out` 包括一个整数,表示可以在这个地区的所有树冠上觅食的猴子数。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

3

## 提示

【数据规模】

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

对于全部的数据,保证有 $2 <= N <= 1000$,$1 <= M <=500$

感谢@charlie003 修正数据
2023/9/4 12:59
加载中...