【牛客小白月赛22】NC202505 工具人

本场比赛通过人数只有十几人的数学毒瘤题qwq。。关于此题讲解好像也不多，要先了解基本的弧度知识，初中蒟蒻瑟瑟发抖

在@Marco.L.T. dalao的帮助下，小蒟蒻勉强通过了本题（下面的代码是在Marco.L.T.代码的基础上稍微改进的）

先把代码放这qwq，等小蒟蒻完全弄懂了，会来不断完善本篇题解的！

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct node {
    double x,y,l,r;
} p[505];
inline bool cmp(node a,node b) {
    return a.l<b.l;
}
const double pi=acos(-1);//acos()是反余弦函数，cosπ = -1，所以π = acos(-1)。
double pl[505],pr[505],maxr[505],r;
int main() {
    int n,T,cnt,cnt2,ans,pos,tot;
    double d,dis,si,otg,t,tg;

    scanf("%d",&T);
    while(T--) {
        scanf("%d%lf",&n,&d),cnt=0;
        for (int x,y,i=1; i<=n; i++) {
            scanf("%d%d",&x,&y);
            dis=sqrt(x*x+y*y);//计算到原点距离
            if (dis<=d) continue;//由于射线都是以原点为端点，所以dis<=d则任一条射线都可覆盖到，略过此点

            si=d/dis,otg=si/sqrt(1-si*si);//计算可行的夹角区间（在这个区间内的射线到点(x,y)的距离都小于d，即可以覆盖到），otg是两条切线夹角的1/2(见下图)）
            t=atan(otg),tg=atan2(y,x);//atan可返回数字的反正切值

            while(tg-t<0) tg+=2*pi;
            while(tg-t>2*pi) tg-=2*pi;//加减2pi就是保证所有角度在一圈以内（因为x+2pi和x表示的角度相同）
            p[++cnt]=(node) {
                x,y,tg-t,tg+t
            };
        }

        sort(p+1,p+cnt+1,cmp);

        if (cnt) {
            ans=cnt;//最多要cnt条射线
            for(int i=1; i<=cnt; i++) {
                cnt2=0;

                for (int j=i; j<=cnt; j++)
                    pl[++cnt2]=p[j].l,pr[cnt2]=p[j].r;
                for (int j=1; j<i; j++)
                    pl[++cnt2]=p[j].l+2*pi,pr[cnt2]=p[j].r+2*pi;

                pos=1,tot=0,maxr[cnt]=pr[cnt];
                for (int j=cnt-1; j; j--) maxr[j]=min(maxr[j+1],pr[j]);
                while(pos<=cnt) {

                    r=maxr[pos];
                    while(pos<=cnt && pl[pos]<=r) pos++;
                    tot++;
                }
                ans=min(ans,tot);
            }
            printf("%d\n",ans);
        } else puts("1"); //由于病毒数n>=0，如果病毒到圆心距离<=d，至少需要一条直线
    }
}