题解 | #喷水装置#

思路：圆的半径小于等于W/2时，他会存在边角，使草坪不能有效覆盖，而当半径大于W/2时，他能覆盖的有效距离可以看成【L-sqrt(r^2-(W/2)^2，L+sqrt(r^2-(W/2)^2】再用区间覆盖判断是否最大可到达L

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct w 
{
    double l;
    double r;
};
struct w a[15010];
bool cmp(struct w x,struct w y)
{
    return x.l<y.l;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        double L,W;
        int ans=0;
        cin>>n>>L>>W;
        int h=0;
        for(int i=0;i<n;i++)
        {
            double l,r;
            cin>>l>>r;
            if(r>W/2.0)
            {
                a[h].l=(double)l-sqrt(r*r-(W*W)/4);
                a[h].r=(double)l+sqrt(r*r-(W*W)/4);
                h++;
            }
        }
        sort(a,a+h,cmp);
        double idx=0；//上一次最大到达位置
        double mx=0;//每次最大到达的位置
           for(int i=0;i<h;i++){
               for(int j=i;j<h;j++){
                if(a[j].r>idx&&a[j].l<=idx){ //是否可到达这一位置
                    if(mx<a[j].r) mx=a[j].r;//单次到达最大位置
                } 
                else if(a[i].l>idx)
                    break;
               }
               ans++; 
               idx=mx; 
               if(idx>=L) break;
          }
          if(idx>=L) cout<<ans<<"\n";
          else cout<<-1<<"\n";
    }
    return 0;
}