学步园

/*************************************************************
题意：给你一些点，要做一些从原点出发的射线使这些点到最近的射线的距离都不超过 d ，求最少需要做多少根射线
思路：算出每个点到与它距离不大于 d 的射线的角度的区间，然后就是区间选点的问题了，贪心
由于这是一个圈，所以要从每个开始都算一下，一个简单的方法就是把它拓展一倍
**************************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int pn;
const double PI = acos(-1);
const double eps = 1e-9;
int cmp(double x)
{
    if(x < -eps) return -1;
    if(x > eps) return 1;
    return 0;
}

struct Point
{
    double l, r;
    Point(): l(0.0), r(0.0){}
}p[777];

bool radCmp(const Point &a, const Point &b){return a.r < b.r;}

int solve()
{
    double pre;
    int ans = pn, t;
	sort(p, p + pn, radCmp);
	for (int i = 0; i < pn; i++) {
		p[i + pn].l = p[i].l + 2 * PI;
		p[i + pn].r = p[i].r + 2 * PI;
	}
    for(int i = 0; i < pn; i++)
    {
        int tmp = 1;
        pre = p[i].r;
        for(t = i + 1; t - i < pn; t++)
        {
            if(cmp(p[t].l - pre) > 0)
            {
                tmp++;
                pre = p[t].r;
            }
        }
        ans = min(ans, tmp);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, d, i, x, y;
        double tmp;
        scanf("%d %d", &n, &d);
        pn = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &x, &y);
            int ds2 = x * x + y * y;
            if(ds2 <= d * d) continue;
            p[pn].l = p[pn].r = atan2(1.0 * y, 1.0 * x);
            tmp = asin(1.0 * d / sqrt(1.0 * ds2));
            p[pn].l -= tmp;
            p[pn].r += tmp;
            if(cmp(p[pn].r - PI) > 0)
            {
                p[pn].r -= 2 * PI;
                p[pn].l -= 2 * PI;
            }
            pn++;
        }
        printf("%d\n", solve());
    }
    return 0;
}