题都快看蒙了，怎么做

Question

长L米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
Picture1
输入格式：
输入包含若干组测试数据。
第一行一个整数 T 表示数据组数；
每组数据的第一行是整数n 、L 和 W；
接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。
输出格式：
输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出“-1”。
样例输入：
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
样例输出：
6
2
-1
约定：
n<=15000
就想不出来排序

Answer 1

贪心问题,因为是一块草地,所以要考虑长和宽,宽的话只需要在输入数据的时候考虑一下半径,如果半径小于等于宽的二分之一就直接略过,在考虑长的时候不能以喷水的最长去考虑,要考虑和草地的交点,同时要考虑交点和交点之间要连起来或者互相覆盖,交点的计算公式为:start=x-sqrt(radius^2-(w/2)^2),end=x+sqrt(radius^2-(w/2)^2),并把最后一个end求出来,如果大于长,就说明可以,否则输出-1.

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
using namespace std;
#define MAX_NUM 15001

typedef struct Sprayer {
    double location;
    double radius;
    double inter_point_start;
    double inter_point_end;
}Spr[MAX_NUM];

int cmp(Sprayer a, Sprayer b) {
    return a.inter_point_start < b.inter_point_start;
}

int main()
{
    int T;
    Spr spr;
    cin >> T;
    for (int k = 1; k <= T; k++) {
        int n, cnt = 0;
        double L, W;
        cin >> n >> L >> W;
        for (int i = 1; i <= n; i++) {
            cin >> spr[i].location >> spr[i].radius;
            if (spr[i].radius <= W / 2)
                continue;
            //cout<<"jiance"<<endl;
            cnt++;
            spr[cnt].inter_point_start = spr[i].location - sqrt(spr[i].radius * spr[i].radius - W * W / 4.0);//cout<<"a[cnt].x"<<"Ϊ"<<spr[cnt].inter_point_start<<endl;
            spr[cnt].inter_point_end = spr[i].location + sqrt(spr[i].radius * spr[i].radius - W * W / 4.0);//cout<<"a[cnt].x"<<"Ϊ"<<spr[cnt].inter_point_end<<endl;
        }
        sort(spr + 1, spr + cnt + 1, cmp);
        //cout<<"jiance2"<<endl;
        int min_num = 0;
        double Sum = 0;
        int flag = 1;
        int i = 1;
        while (Sum < L) {
            min_num++;
            double t = Sum;
            for (; spr[i].inter_point_start <= t && i <= cnt; i++)//
                if (Sum < spr[i].inter_point_end)
                {
                    Sum = spr[i].inter_point_end;
                    //cout<< Sum<<"是多少";
                }
            if (t == Sum && t < L) {
                cout << "-1" << endl;
                flag = 0;
                break;
            }
        }

        if (flag)
            cout << min_num << endl;
    }

}