UVA1193 Radar Installation

    • 146通过
    • 477提交
  • 题目来源 UVA 1193
  • 评测方式 RemoteJudge
  • 标签 优先队列 排序 贪心
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    描述:

    假设海岸线是一条无限长的直线,陆地位于海岸线的一边,大海位于海岸线的另一边。大海中有许多小岛。某安全部门为了监视这些岛上是否有敌人入侵,打算在海岸线上安装若干个雷达来检测岛屿的情况。每个雷达的覆盖范围是以雷达中心为圆心,半径为d的圆形区域。

    我们用平面之间坐标系来表示整个区域,海岸线为x轴,大海位于x轴上方,陆地位于x轴下方。为了节约成本,安全部门想使用最少的雷达覆盖所有的岛屿。现在已知每个岛屿的坐标(x,y)和雷达的覆盖半径d,你的任务就是计算出能够覆盖所有岛屿的最少雷达数量。

    输入:

    输入包含若干组数据。每组数据的第一行有两个整数n(1<=n<=1000)和d,分别表示岛屿的数量和雷达的覆盖半径,之后的n行,每行有两个整数,表示第i个岛屿的坐标(xi,yi),相邻的两组数据使用一个空行隔开。输入“0 0”表示输入结束。

    输出:

    对于每一组数据的输出格式为“Case i: x”,表示第i组数据中最少需要x个雷达来覆盖所有的岛屿;x=-1表示这组数据无解(无法覆盖所有的岛屿)

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

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