题目传送门

思路:对于每个点都可以通过一些简单计算得到激光枪射中它的最小角度和最大角度,将这些角度排序,枚举起点。

在遍历过程中,对最小角度我们都对这个点进行标记,如果遇到最大角度,那么所有之前标记的点都可以被射中,那么我们就讲这些点的标记清空,最后取最小值即可

时间复杂度$O(n^2)$

/*
 *
 * Author: Hsueh-
 * Date: 2020-03-02 13:10:34
 *
 * */

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

#define endl "\n"
#define all(A) A.begin(), A.end()
using ll = long long;
using db = double;
using pII = pair<int, int>;

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int N = 5e2 + 10;
const db eps = 1e-8, PI = acos(-1.0);

int sgn(db x) {
    if (fabs(x) < eps)
        return 0;
    else
        return x > 0 ? 1 : -1;
}

struct node {
    int type;
    int idx;
    db angle;

    node() {}

    node(int type, int idx, db _angle) : type(type), idx(idx) {
        angle = fmod(_angle + 2 * PI, 2 * PI);
    }

    bool operator<(const node& other) const {
        if (sgn(angle - other.angle) == 0)
            return type < other.type;
        else
            return angle < other.angle;
    }
};

int n, d;
vector<node> vec;
int mark[N];

void RUN() {
    cin >> n >> d;
    vec.clear();
    for (int i = 1; i <= n; ++i) {
        db x, y;
        cin >> x >> y;
        db dis = x * x + y * y;
        if (sgn(dis - d * d) <= 0)
            continue;
        db angle = atan2(y, x);
        db sub = asin(d / sqrt(dis));
        vec.push_back(node(0, i, angle - sub));
        vec.push_back(node(1, i, angle + sub));
    }
    if (vec.empty()) {
        cout << 1 << endl;
        return;
    }
    sort(all(vec));
    int res = vec.size() / 2;
    // for (auto it : vec) {
    //     dbg(it.idx);
    // }
    for (int i = 0, len = vec.size(); i < len; ++i) {
        vector<int> l;
        memset(mark, 0, sizeof mark);
        int tmp = 0;
        for (int k = 0; k < len; k++) {
            int j = (i + k) % len;
            if (vec[j].type == 0) {
                mark[vec[j].idx] = true;
                l.push_back(vec[j].idx);
            } else if (mark[vec[j].idx]) {
                tmp++;
                for (auto it : l) {
                    mark[it] = 0;
                }
                l.clear();
            }
        }
        tmp += l.size();
        res = min(res, tmp);
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int T;
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        RUN();
    }

    return 0;
}