------题解------

thomaswcy 2020-11-28 14:44:40 33 返回题目

#include<bits/stdc++.h>
using namespace std;
typedef struct Sprayer{
 double l;
 double radius;
 double start;
 double end;
}Spr[15010];
int cmp(Sprayer a,Sprayer b)
{
    return a.start<b.start;
}
int main()
{
  int T;
  Spr spr;
  cin>>T;
  for(int i=1;i<=T;i++)
  {
    int n,cnt = 0;
    double L,W;
    cin>>n>>L>>W;
    for(int i=1;i<=n;i++)
	{
       cin>>spr[i].l>>spr[i].radius;
       if(spr[i].radius <= W/2)
        continue;
        cnt++;
       spr[cnt].start = spr[i].l-sqrt(spr[i].radius*spr[i].radius-W*W/4.0);
       spr[cnt].end = spr[i].l+sqrt(spr[i].radius*spr[i].radius-W*W/4.0);
    }
    sort(spr+1,spr+cnt+1,cmp);
    int minn = 0;
    double Sum = 0;
    int flag = 1;
    int i=1;
    while(Sum < L)
	{
        minn++;
        double t = Sum;
        for(;spr[i].start <= t && i<=cnt;i++)
            if(Sum < spr[i].end)
             {
                 Sum = spr[i].end;
             }
        if(t==Sum && t<L)
		{
            cout<<"-1"<<endl;
            flag = 0;
            break;
        }
	}
	if(flag)
    	cout<<minn<<endl;
  }

}
{{ vote && vote.total.up }}