跟浮点数有关的题都简单不到哪去。

难度： 绿

算法标签： 贪心

这道题没什么难度，主要是调代码。具体解析可以看一本通或洛谷题解。

注意： 不能覆盖宽度的水龙头要无视掉。我因此调了 $3$ 个小时。

#include<bits/stdc++.h>
using namespace std;
int tc,n,m,w,x,y,ans,bj,j;
double k=1e-12,p,s,t;
struct st{
	double l,r;
}d[20000];
bool cmp(st a,st b){
	if(a.l!=b.l) return a.l<b.l;
	return a.r<b.r;
}

int main(){
	scanf("%d",&tc);
	while(tc--){
		ans=0,bj=1,t=0,j=1;
		scanf("%d%d%d",&n,&m,&w);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&x,&y);
			if(y<=w/2){				
				i--;
				n--;
				continue;
			}
			d[i].l=max(0.0,double(x)-sqrt(y*y*1.0-(w/2.0)*(w/2.0)));
			d[i].r=min(m*1.0,double(x)+sqrt(y*y*1.0-(w/2.0)*(w/2.0)));
		}
		sort(d+1,d+n+1,cmp);
		while(t<m){
			ans++;
			s=t;
			for(;d[j].l<=s&&j<=n;j++) t=max(t,d[j].r);
			if(s==t&&s<m){
				printf("-1\n");
				bj=0;
				break;
			}
		}
		if(bj) printf("%d\n",ans);
	}
	return 0;
}