| 题目名称 | 3187. [POJ 1328]监控安装 |
|---|---|
| 输入输出 | monitor.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2019-06-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：73， 通过率：17.81% | ||||
 reØreOré |
100 | 0.000 s | 0.00 MiB | C++ |
 yrtiop |
100 | 0.000 s | 0.00 MiB | C++ |
|
op_组撒头屯 |
100 | 0.000 s | 0.00 MiB | C++ |
|
syzhaoss |
100 | 0.000 s | 0.00 MiB | C++ |
 菜鸟 |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
Nj_L |
100 | 0.030 s | 3.34 MiB | C++ |
|
元始天尊 |
100 | 0.031 s | 3.37 MiB | C++ |
|
Nj_L |
100 | 0.033 s | 3.38 MiB | C++ |
|
三玖是我老婆 |
100 | 0.033 s | 3.61 MiB | C++ |
| 关于 监控安装 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
审题！审题！审题！
| ||||
【题目描述】
校长想通过监控设备覆盖学校内的$N$座建筑物，每座建筑物被视为一个点，在坐标系中给出坐标为($x$, $y$)，并且所有的建筑物都在$x$轴的上方。因为学校的供电和传输线路均沿$x$轴，所以监控设备只被允许建立在$x$轴上。每台监控设备的监控方位均为一个半径为$R$的圆，圆心即为监控设备。现在给出$N$座建筑物的坐标，问最少需要几台这样的设备可以实现对所有建筑物的监控？
【输入格式】
第一行：两个整数N（$1\leq N \leq 1000$）和$R$；
接下来$N$行：每行有两个整数表示建筑物的坐标。
【输出格式】
输出只有一行：一个整数表示最少安装监控数，如果不能安装输出-1。
【样例输入】
3 2 1 2 -3 1 2 1
【样例输出】
2