开始: 2022-04-05 19:00:00

2022年4月双周赛(高级班)

结束: 2022-04-05 21:30:00
当前: 2025-06-12 06:20:49  类型:OI 状态:已经结束 
P4 : 贪心进阶-练习-雷达  
描述

有n个二维坐标点。

现在要在x轴上放置若干雷达,每个雷达的辐射半径都是d。

问至少需要几个雷达才能够辐射所有点,如果辐射不到所有的点,则输出-1。

输入

第一行一个整数n(1n1000)n(1 \le n \le 1000)d(1d10000)d(1 \le d \le 10000)

接下来n行,每行输入一个点的坐标。

坐标范围[-10000,10000]。

输出

输出一个整数表示答案。

样例

输入
复制

3 2
1 2
-3 1
2 1

输出
复制

2

输入
复制

1 2
0 2

输出
复制

1
提示

【样例1说明】

16889068213480.png