| 比赛场次 | 667 |
|---|---|
| 比赛名称 | 贪心题目练习 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2025-03-22 08:00:00 |
| 结束时间 | 2025-03-23 16:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 请使用文件输入输出 |
| 题目名称 | 监控安装 |
|---|---|
| 输入输出 | monitor.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 OTTF |
AAAAAAAAAA | 0.035 s | 3.46 MiB | 100 |
|
Cogito |
AAAAAAAAAA | 0.036 s | 3.38 MiB | 100 |
|
duck |
AAAAAAAAAA | 0.038 s | 3.51 MiB | 100 |
|
TeaWine |
AAAAAAAAWA | 0.034 s | 3.37 MiB | 90 |
|
李金泽 |
WWWAAAWWWW | 0.020 s | 1.94 MiB | 30 |
|
秋_Water |
RRRRRRRRRR | 2.050 s | 3.06 MiB | 0 |
【题目描述】
校长想通过监控设备覆盖学校内的$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