← 返回题目列表

AtCoder · awc0069_d

D. 无线电塔的安装

中文机器翻译题面 查看原题

分数: 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