loj 10002

题目分析：

• 经典的区间覆盖问题
• 我们需要用勾股定理预处理出一个喷头的左右区间
• 如果一个喷头的 $r\&lt;=\left(h/2\right),continue$r<=(h/2),continue, $r==\left(h/2\right)$r==(h/2)的时候为什么不要呢，因为它只覆盖了一个点
• 按照喷头的 $l$l从小到大排序，每次对于当前的左界，在 $e\left[i\right].l\&lt;=t$e[i].l<=t的情况下，使 $e\left[i\right].r$e[i].r尽可能的大，然后更新左界为 $e\left[i\right].r$e[i].r，如果找不到来更新 ，无解

Code :

#include <bits/stdc++.h>
using namespace std;
#define maxn 15010

int T,n,L,h,cnt=0;
struct node {
	double l,r;
}e[maxn];

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

inline void work_() {
	double t=0;
	int i=1,ans=0;
	while(t<L) {
		double s=t;
		for( ;i<=cnt&&e[i].l<=t;++i) {
			if(e[i].r>s) s=e[i].r;
		}
		if(s==t) {
			printf("-1\n");
			return;
		}
		++ans;
		t=s;
	}
	printf("%d\n",ans);
}

inline bool cmp_(node aa,node bb) {
	if(aa.l==bb.l) return aa.r > bb.r;
	return aa.l < bb.l;
}

void readda_() {
	T=read_();
	while(T--) {
		n=read_();L=read_();h=read_();
		int x,y;cnt=0;
		for(int i=1;i<=n;++i) {
			x=read_();y=read_();
			if(y<=(h/2)) continue;
			e[++cnt].l=(double) x-sqrt( (double) y*y-h*h/4.0);
			e[cnt].r=(double) x+sqrt( (double) y*y-h*h/4.0);
		}
		sort(e+1,e+cnt+1,cmp_);
		work_();
	}
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}