分数: 400 分
问题陈述
高桥是一名工程师,负责开发某个地区的通信基础设施。
有 N 该地区的村庄,沿着笔直的道路分布在不同的位置。村庄 i 位于 X_i 距道路起点 米,海拔为 P_i 米。两个村庄之间的距离 i, j 定义为 |X_i - X_j| 米(海拔差异不影响距离)。
高桥需要在一些村庄安装无线电塔,以便向所有村庄传送无线电信号。无线电塔只能安装在海拔至少为 K 米(即一个村庄 i 满意 P_i \geq K)。标高只影响能否安装无线电塔,不影响无线电信号的范围。
距离内的所有村庄 D 距离安装无线电塔的村庄米或以内可以接收该塔的信号(安装塔的村庄也可以接收信号,因为距离为 0)。距离村庄超过 D 仪表无法接收信号。最大信号范围 D 对于所有无线电塔都是相同的。
每个村庄必须能够从至少一个无线电塔接收信号。
高桥希望在满足此条件的同时尽量减少安装的无线电塔数量。如果存在满足条件的无线电塔放置位置,请找出所需的最少无线电塔数量。如果不存在有效放置,则输出 -1.
无法满足条件的情况示例包括:当不存在可以安装无线电塔的村庄时,或者当存在无法位于距离内的村庄时 D 任何可以安装无线电塔的村庄。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq D \leq 10^9
- 0 \leq X_i \leq 10^9
- 1 \leq P_i \leq 10^9
- X_i \neq X_j (i \neq j)
- 所有输入值均为整数
- 村庄不一定按位置升序排列 X_i
输入
N K D X_1 P_1 X_2 P_2 \vdots X_N P_N
- 第一行包含村庄数量 N,最低海拔 K 安装无线电塔所需的最大信号范围 无线电塔的 D ,由空格隔开。
- 从第 2 行到 (N + 1)第行,给出了每个村庄的信息。
- 的 (1 + i)第行包含位置 X_i 距道路起点及标高 P_i 村 i,以空格分隔。
输出
如果存在可以向所有村庄传送信号的无线电塔的位置,则输出一条线路中所需的无线电塔的最少数量。如果不存在这样的位置,则输出 -1.
示例输入 1
5 100 10 0 50 5 150 15 80 25 200 30 60
示例输出 1
2
示例输入 2
4 500 5 0 100 10 200 20 300 30 400
示例输出 2
-1
示例输入 3
10 50 15 0 100 8 30 20 60 25 40 35 80 50 55 60 20 75 90 85 45 100 70
示例输出 3
4