题目描述

某国的政府正在规划修建地铁。出于其本国实际考虑，他们希望每一条地铁线路都从首都中心，即原点 $(0,0)$ 出发，然后以某个角度向外直线延伸。对于每一个城市，要求离该城市最近的地铁线与该城市的距离不能超过 $d$。

给定该国的所有城市的坐标，你需要求出最少需要多少条线路能够满足上述条件。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行两个整数 $n,d$，表示该国的城市数量和地铁线路与城市间的最大距离。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示第 $i$ 个城市的坐标是 $(x_i,y_i)$。

输出格式

对于每组数据，一行一个整数表示满足条件下最少需要的地铁线路个数。

2
7 1
-1 -4
-3 1
-3 -1
2 3
2 4
2 -2
6 -2
4 0
0 4
-12 18
0 27
-34 51

4
2

数据规模与约定

$1\le n\le 500$，$0\le d<150$，对 $1\le i\le n$ 都有 $-100 \le x_i,y_i\le 100$，任意两个城市的坐标都不相同。

题目来源

POJ3004

Svenskt Mästerskap i Programmering/Norgesmesterkapet 2003