向往的气球
时间: 1ms 内存:128M
描述:
一年一度的计控ACM院赛即将来临。除了ACMers以外,志愿者们也非常的忙碌。他们需要将各种颜色的气球分配给A掉相应题目的队伍。现在,所有比赛队伍的成员都处在一个房间中,这个房间是一个二维坐标系,大小为1000行x1000列。
每一个坐标对应着空座位或某个参赛队伍。每一分钟,志愿者们都应该把所有的气球聚集在一起。志愿者将会被告知把气球送到哪里。为了保证工作的效率,对于两个坐标(x1,y1)和(x2,y2),如果|x1-x2|不大于k 或者 |y1-y2|不大于k,则这两个坐标的气球由同一个志愿者配送。你能知道最少需要多少志愿者,才能配送完所有的气球吗?
输入:
第一行包含一个整数T,表示有T组数据。
对于每一组数组,这里将有n+1行
第一行:输入两个整数n,k; n表示气球的数量,k表示题目中的k值
接下来的n行中,每一行包含两个整数r,c。表示气球应该被送往r行,c列。请注意坐标可能会相同。
题目中保证:T<=100,1<=n<=10000,1<=k,r,c<=1000
输出:
对于每一组数据,你需要输出一行
输出最少需要的志愿者数量
示例输入:
2
3 5
1 1
10 6
15 20
2 5
1 1
7 7
示例输出:
1
2
提示:
参考答案:
文章评论