3 条题解

  • 5
    @ 2021-8-7 18:41:43

    C++ :

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    typedef pair<double, double> PDD;
    const int N = 1010;
    const double eps = 1e-6, INF = 1e10; // double一般定义一个eps精确值
     
    int n, R;
    PDD segs[N];
    
    int main()
    {
        bool success = true;
        
        cin >> n >> R;
        for(int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            if(y > R)
            {
                success = false;
                break;
            }
            double len = sqrt(R * R - y * y);
            segs[i] = {x + len, x - len}; //区间 按终点起点排序
        }
        if(!success) puts("-1");
        else
        {
            sort(segs, segs + n);
            int res = 0;
            double last = -INF; //***这里要定义double
            for(int i = 0; i < n; i++)
            {
                auto seg = segs[i];
                if(seg.second > last + eps) //seg.second 是起点
                {
                    res ++;
                    last = seg.first; // seg.first的终点
                    
                }
            }
            cout << res << endl;
        }
        return 0;
    }
    
    • 0
      @ 2024-6-15 19:57:51
      #include <cstring>
      #include <string.h>
      #include <queue>
      #include <stack>
      #include <map>
      #include<iostream>
      using namespace std;
      int main(){
      for (int i = 1;i <= 514514;i++)
      { 
          cout<<"11111111111111111111111111111111111111111111111111111111111111111111111111111111111111"; 
      }
           return 0;  
      }
      

      AC

      • 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~ ~定过~

        • 1

        信息

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