/*
* 区间覆盖思路:
* 1. 将所有子区间按照左端点升序排序
* 2. 从小开始枚举所有子区间,找到所有在st之前的区间,在这些区间中找到最大的右端点(while部分)
* 3. 如果最大右端点r < st,说明无法覆盖,提前退出输出-1
* 4. 反之,找到了一个合法区间,cnt ++;
* 5. 如果 r >= ed,完成覆盖,退出循环,输出最少区间个数
* 6. 更新左端点st = r, 继续以本次最大右端点作为下一次查找的左端点,重复上述步骤
* 7. 对于i = j - 1, 目的是让下次,i从不 满足左端点在st之前的第一个区间 进行操作
* !!!!!!!!!!!!st和ed一定要是double!!!!!!,
*
* 调试了俩小时
*
* /
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<double, double> PDD;
int T;
double n, L, W;
int main() {
cin >> T;
while (T --) {
vector<PDD> res;
cin >> n >> L >> W;
for (int i = 0; i < n; i ++ ) {
double loc, R;
cin >> loc >> R;
if (R <= W / 2) continue;
double d = sqrt(R * R - W * W / 4.0);
double left = loc - d, right = loc + d;
res.push_back({left, right});
}
sort(res.begin(), res.end());
/**
* 区间覆盖思路:
* 1. 将所有子区间按照左端点升序排序
* 2. 从小开始枚举所有子区间,找到所有在st之前的区间,在这些区间中找到最大的右端点(while部分)
* 3. 如果最大右端点r < st,说明无法覆盖,提前退出输出-1
* 4. 反之,找到了一个合法区间,cnt ++;
* 5. 如果 r >= ed,完成覆盖,退出循环,输出最少区间个数
* 6. 更新左端点st = r, 继续以本次最大右端点作为下一次查找的左端点,重复上述步骤
* 7. 对于i = j - 1, 目的是让下次,i从不 满足左端点在st之前的第一个区间 进行操作
* */
// cout << "res.size(): " << res.size() << endl;
// for (int x = 0; x < res.size(); x ++) {
// cout << x + 1 << ": " << res[x].first << "--> " << res[x].second << "\n";
// }
/**
* !!!!!!!!!!!!st和ed一定要是double!!!!!!,
*
* 调试了俩小时
*
* */
double st = 0, ed = L, cnt = 0; bool success = false;
for (int i = 0; i < res.size(); i ++ ) {
int j = i; double r = -INF;
while (j < res.size() && res[j].first <= st) {
r = max(r, res[j].second);
j ++;
}
// 1. r < st,无法覆盖草地,出现断区间
if (r < st) {
cnt = -1;
break;
}
cnt ++;
// 2. r >= L, 覆盖整块草地
if (r >= ed) {
success = true;
break;
}
// 3. r 在草地长度范围内,继续进行
i = j - 1;
st = r;
}
if (!success) cnt = -1;
cout << cnt << endl;
}
return 0;
}
// 8 20 2
// 5 3
// 4 1
// 1 2
// 7 2
// 10 2
// 13 3
// 16 2
// 19 4