4 条题解

  • 0
    @ 2023-1-24 20:53:45
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    
    const int N=1010;
    int n,d;
    struct Segment
    {
        double l,r;
        bool operator < (const Segment& t) const
        {
            return r<t.r;
        }
    }seg[N];
    int main()
    {
        cin>>n>>d;
        bool failed=false;
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            //将平面问题转化到横轴上的一个个区间
            if(y>d) failed=true;   //如果比半径大,直接fail
            else
            {
                double len=sqrt(d*d-y*y);
                seg[i].l=x-len,seg[i].r=x+len; //区间左端点l,区间右端点r       
            }
        }
        if(failed)
            puts("-1");
        else
        {
            sort(seg,seg+n);
            int cnt=0;
            double last=-1e20;  //last表示上一个区间的右端点
            for(int i=0;i<n;i++)
            {
                if(last<seg[i].l)   
                {
                    cnt++;  //若下一个区间左端点比上一个区间的右端点小,那么就要再新加一个圆
                    last=seg[i].r;  //更新
                }
            }
            cout<<cnt;
        }
    
        getchar();getchar();
        return 0;
    }
    
    

    ~111~ ~定过~

    信息

    ID
    24
    时间
    1000ms
    内存
    128MiB
    难度
    2
    标签
    递交数
    137
    已通过
    89
    上传者