记录编号	570845	评测结果	AAAAAA
题目名称	喷水装置	最终得分	100
用户昵称	dew52	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2022-04-20 20:34:05	内存使用	3.63 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 1e5 + 5;
struct Node
{
    double lx;
    double ly;
}a[MAXN];
int T, L, W, n;
double h;
double cal (int R);
int cmp (Node x, Node y);
int main()
{
    freopen("sprinkler.in","r",stdin);
    freopen("sprinkler.out","w",stdout);
    scanf("%d", &T);
    while (T--)
    {
        //puts("####################");
        scanf("%d%d%d", &n ,&L, &W);
        h = 1.0 * W / 2;
        for (int i = 1; i <= n; ++i)
        {
            double x, R;
            scanf("%lf%lf", &x, &R);
            double r = 0.0;
            if (R > h)
            {
                r = cal(R);
            }
            else r = 0.0;
            a[i].lx = x - r;
            a[i].ly = x + r;
        }
        sort (a + 1, a + n + 1, cmp);
        /**************************/
        int cnt = 0;
        double pos = 0.0, last = 0.0;
        for (int i = 1; i <= n; ++i)
        {
            if (a[i].lx <= pos)
            {
                last = a[i].ly;
                /*寻找最大的右坐标*/
                while (a[i].lx <= pos)
                {
                    last = max(last, a[i].ly);
                    i++;
                    if (i == n + 1)
                    break;
                }
                pos = last;
                i--;
                cnt++;
            }
            if (pos >= L) break;
        }
        if (pos >= L) cout << cnt << endl;
        else puts("-1");
        //puts("********************");
    }
    return 0;
}
double cal (int R)
{
    return sqrt(R * R - h * h);
}
int cmp (Node x, Node y)
{
    return x.lx < y.lx;
}