编程题
### 问题描述 在神秘的魔法世界里,存在一个名为 Astralos 的大陆。Astralos 大陆上的精灵们居住在浮空的水晶宫殿中。为了确保每个水晶宫殿都能被神秘的魔法之光照到,魔法之塔需要在地面上刻下一些魔法阵。每个魔法阵都有固定的光照范围,并且所有魔法阵都要在某一个水平线以下(包括在这条线上)。你的任务是确定为了确保每个水晶宫殿都被魔法之光照到,最少需要刻下多少个魔法阵。若不可能照亮所有水晶宫殿,则输出 $NO$。 ### 输入格式 第一行:三个整数,分别表示水晶宫殿的数量 $n$ ,魔法阵的光照范围 $d$ 和水平线的 $y$ 轴(可为负数)坐标 $z$。(整个魔法世界投射在一个二维平面坐标系内) 接下来的 $n$ 行:每行两个整数,表示水晶宫殿的坐标。 ### 输出格式 输出一个整数,表示最少需要的魔法阵数量。若不可能照亮所有水晶宫殿,则输出 $NO$。 ### 样例输入 ```text 3 2 1 1 2 2 2 1 1 ``` ### 样例输出 ```text 1 ``` ### 说明 对于样例,当魔法阵建在水平线上,并且 $x$ 轴坐标在 $[1,2]$ 之间时,明显可以完全覆盖三个水晶宫殿。 ### 评测数据规模 对于 $50$% 的评测数据,水晶宫殿的数量 $n \le 10$,$d \le 2 \times 10^4$,$|z|\le 1\times 10^3$,水晶宫殿的 $x$ 坐标满足 $|x_i| \le 2 \times 10^6$,y 坐标满足 $z \le y_i \le 2 \times 10^4$。 对于 $100$% 的评测数据,$n \le 2000$,$d \le 2 \times 10^4$,$|z|\le 1\times 10^3$,水晶宫殿的 $x$ 坐标满足 $|x_i| \le 2 \times 10^6$,y 坐标满足 $z \le y_i \le 2 \times 10^4$。
查看答案
赣ICP备20007335号-2