P2504 [HAOI2006]聪明的猴子

    • 1.2K通过
    • 3.5K提交
  • 题目提供者 c41113
  • 评测方式 云端评测
  • 标签 Kruskal 生成树 各省省选 2006 河南 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

    输入输出格式

    输入格式:

    输入文件monkey.in包括:

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

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

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

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

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

    输出格式:

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

    输入输出样例

    输入样例#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 修正数据

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。