问题1681--Frost Ring

1681: Frost Ring

时间限制: 1 Sec  内存限制: 128 MB
提交: 235  解决: 97
[状态] [讨论版] [提交] [命题人:]
题目描述

伟大的亡灵巫师山德鲁研究出了一个高深的魔法“寒冰魔环”,自从有了这个魔法,所有的生物都十分惧怕他。

寒冰魔环的魔法效果如图所示 ”能伤及目标附近的士兵但不伤及目标”。假设寒冰魔环的伤害范围为一个半径为R的圆,当寒冰魔环命中一个敌方士兵时,命中的这个士兵不会受伤害,但他周围半径为R范围内的所有士兵将受到伤害。

现在山德鲁遇到了一场恶战,他需要使寒冰魔环命中一个最佳目标(一个敌方士兵),以伤害尽可能多的敌方士兵,方能取得战斗的胜利。他已知道了每个敌方士兵的位置(为一个平面直角坐标系坐标)。现在他需要知道第一次使用寒冰魔环最多能伤及到多少个敌方士兵。


输入

首先输入一个整数T,代表有T组测试实例。(1<=T<=10)
对于每组测试实例,第一行输入两个整数n、R,分别代表有n个敌方士兵和寒冰魔环的伤害半径R。(0<=n<1000,1<=R<=1000)
接下来输入n行,每行输入两个整数xi、yi,代表第i个敌方士兵的坐标。并保证任意两个敌方士兵不在同一个坐标上。(0<=xi,yi<=1000)
输出

对于每组实例,输出一个整数占一行,代表第一次释放寒冰魔环最多能伤及到多少个敌方士兵。

样例输入 Copy
2
4 5
0 0
0 2
3 4
6 2
3 5
1 2
3 2
5 0
样例输出 Copy
3
2
来源/分类