题意分析

题目要求从中央车站$(0,0)$出发，建立若干条直线地铁线路，使得所有重要地点到最近地铁线路的距离不超过$d$。我们需要计算最少需要多少条这样的地铁线路。

解题思路

1. 角度范围计算：对于每个重要地点$(x,y)$，计算其与中央车站的距离$L$。若$L \leq d$，则该点已被覆盖，可以忽略。
2. 角度区间确定：对于未被覆盖的点，计算其能被覆盖的角度区间$[\theta-\alpha, \theta+\alpha]$，其中$\theta$是该点相对于中央车站的角度，$\alpha = \arcsin(d/L)$。
3. 区间覆盖问题：将角度区间转换为环形区间覆盖问题，使用贪心算法求解最少数量的区间覆盖。

实现步骤

1. 输入处理：读取所有重要地点的坐标，过滤掉距离不超过$d$的点。
2. 角度区间计算：计算每个点的角度区间$[l,r]$。
3. 环形区间处理：将角度区间复制一份并偏移$2\pi$，以处理环形特性。
4. 贪心选择：对每个起始区间，选择尽可能多的重叠区间，统计最少需要的区间数量。

C++实现

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 555;
const double PI = acos(-1);
const double eps = 1e-8;

struct Point {
    double x, y, l, r;
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    bool operator < (const Point &a) const { return l < a.l; }
};

Point pt[MAXN<<1];

int main() {
    int t, n;
    double d;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%lf", &n, &d);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            double x, y;
            scanf("%lf%lf", &x, &y);
            double dist = sqrt(x*x + y*y);
            if (dist <= d + eps) continue;
            double alpha = asin(d / dist);
            double theta = atan2(y, x);
            pt[cnt].x = x;
            pt[cnt].y = y;
            pt[cnt].l = theta - alpha;
            pt[cnt].r = theta + alpha;
            cnt++;
        }
        n = cnt;
        sort(pt, pt + n);
        for (int i = 0; i < n; ++i) {
            pt[i+n] = pt[i];
            pt[i+n].l += 2*PI;
            pt[i+n].r += 2*PI;
        }
        int ans = n;
        for (int i = 0; i < n; ++i) {
            int tmp = 1;
            double r = pt[i].r;
            for (int j = i+1; j < i+n; ++j) {
                if (pt[j].l <= r + eps) r = min(r, pt[j].r);
                else {
                    tmp++;
                    r = pt[j].r;
                }
            }
            ans = min(ans, tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}

代码说明

1. 数据结构：使用Point结构体存储坐标和角度区间。
2. 输入处理：过滤掉距离不超过$d$的点，计算剩余点的角度区间。
3. 环形处理：通过复制并偏移$2\pi$来处理环形区间。
4. 贪心算法：对每个起始区间，选择尽可能多的重叠区间，更新最小数量。
5. 输出结果：输出每个数据集的最少地铁线路数量。