比赛 20220418高一小测验 评测结果 AWWWWW
题目名称 喷水装置 最终得分 16
用户昵称 Lesater 运行时间 0.156 s
代码语言 C++ 内存使用 2.98 MiB
提交时间 2022-04-18 20:09:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define P pair<double,double>
P a[15001];
int main()
{
    freopen("sprinkler.in","r",stdin);
    freopen("sprinkler.out","w",stdout);
    int T,n;
    double L,W;
    cin>>T;
    for(int i=1;i<=T;++i)
    {
    cin>>n>>L>>W;
    W=W/2.0;
    for(int j=1;j<=n;++j)
    {
        double d,b;
        cin>>d>>b;
        double c=0;
        if(b*b>W*W)
        {
        c=sqrt(b*b-W*W);
        a[j].first=d-c;
        a[j].second=d+c;
        if(a[j].first<0) a[j].first=0;
        if(a[j].second>L) a[j].second=L;
        }
        else 
        {
        j--;
        n--;
        }
    }
    sort(a+1,a+1+n);
    int tot=0,r=0;
    double p=0;
    while(p<=L)
      {
        if(p==L)
        {
            cout<<tot<<endl;
            break;
        }
        bool flag=true;
        for(int j=r+1;j<=n;++j)
        {
            if(a[j].first<=p)
            {
                flag=false;
                r=j;
            }
        }          
        p=a[r].second;
        tot++;
        if(flag==true) 
        {
            cout<<-1<<endl;
            break;
        }
      }
    }
    return 0;
}