信息学奥赛一本通T1424-喷水装置

解题思路:

注意事项:整体思路是按照喷头的起始位置从小到大进行排序，然后依次放置喷头，直到覆盖整个地块或者没有剩余的喷头可以放置。

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    double start,end;

}a[100000];

bool cmp(node x,node y){ return x.start<y.start;}

int main()

{

    int T,n,L,W; cin>>T;

    while(T--)

    {

        cin>>n>>L>>W;

        for(int i=1;i<=n;i++)

        {

            int p,r;    cin>>p>>r;

            a[i].start=0;

            a[i].end=0;//记入为0，就是不满足

            if(r>=W/2.0)//只有宽度足够的才有用，并被算进

            {

                a[i].start=p-sqrt(r*r-W*W/4.0);

                a[i].end=p+sqrt(r*r-W*W/4.0);

            }

        }

        sort(a+1,a+1+n,cmp);

        int cnt=0;

        double t=0;

        bool flag=1;

        while(t<L)

        {

            cnt++;

            double p=t;//将变量p赋值为t，表示上一个放置点的位置

            for(int i=1;a[i].start<=p&&i<=n;i++)

            {

                if(a[i].end>t)   //现在的喷头的end大于上一个喷头的end

                    t=a[i].end;

            }

            if(p==t&&t<L)//p==t表示上一个喷头与这一个喷头一样，即没有喷头了

            {

                flag=0;

                cout<<-1<<endl;

                break;

            }

        }

        if(flag==1) cout<<cnt<<endl;

    }

    return 0;

}