#P4324. tjoi2012 炸弹

    ID: 3540 传统题 1000ms 256MiB 尝试: 31 已通过: 8 难度: 6 上传者: 标签>难度分类提高+/省选-图论无向连通分量模拟与实现技巧坐标变换计算几何扫描线排序与序列处理滑动窗口数据结构有序集合普通并查集CF2100

tjoi2012 炸弹

[TJOI2012] 炸弹

题目描述

平面上有 nn 枚炸弹,第 ii 枚位于 (xi,yi)(x_i,y_i)。每枚炸弹的爆炸半径都是 rr。当第 ii 枚炸弹爆炸时,所有满足

∣xi−xj∣+∣yi−yj∣≤r|x_i-x_j|+|y_i-y_j|\le r

且尚未爆炸的炸弹 jj 都会被引燃,随后继续触发其他炸弹。

求至少要直接引燃多少枚炸弹,才能让所有炸弹最终爆炸。

输入格式

第一行两个整数 n,rn,r。接下来 nn 行,每行两个整数 xi,yix_i,y_i。

输出格式

一行一个整数,表示最少需要直接引燃的炸弹数量。

样例 #1

样例输入 #1

3 2
0 0
0 2
3 2

样例输出 #1

2

数据规模与约定

对于 30%30\% 的数据,1≤n≤10001\le n\le1000。

对于全部数据,1≤n≤1051\le n\le10^5,0≤r≤1090\le r\le10^9,0≤xi,yi≤1090\le x_i,y_i\le10^9。