记录编号	570859	评测结果	AAAAAA
题目名称	喷水装置	最终得分	100
用户昵称	Tab↹	是否通过	通过
代码语言	C++	运行时间	0.094 s
提交时间	2022-04-20 21:38:01	内存使用	2.93 MiB

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bits/stl_pair.h>
 
using namespace std;
 
typedef pair<float,float> pff;
 
int solve(pff* beg, pff* end, int len){
    int cnt = 0;
    bool solved = false;
    for(float i = 0; i < len; ){
        bool find = false;
        for(pff* cur = end; cur >= beg; --cur){
            if(cur->first != -1){
                if(cur->first - cur->second <= i){
                    i = cur->first + cur->second;
                    cur->first = -1;
                    ++cnt;
                    find = true;
                    break;
                }
            }
        }
        if(!find)
            break;
        if(i >= len && cnt != 0)
            solved = true;
    }
    if(solved)
        return cnt;
    else
        return -1;
}
 
int main(void){
    ifstream fin("sprinkler.in");
    ofstream fout("sprinkler.out");
    int T;
    fin >> T;
    for(int k = 0; k < T; ++k){
        int n;
        float len, wid;
        fin >> n >> len >> wid;
        float wid_half = wid/2.0;
        pff* arr = new pff[n]();
        pff* cur = arr;
        for(float r, p, i = 0; i < n; ++i){
            fin >> p >> r;
            if(r > wid_half){
                *cur = {p, sqrt(r*r - wid_half*wid_half)};
                ++cur;
            }
        }
        if(cur == arr) 
            fout << -1 << endl;
        else{
            sort(arr,cur);
            fout << solve(arr, cur-1, len) << endl;
        }
        delete []arr;
    }
    return 0;
}