作业介绍

#include<bits/stdc++.h>
using namespace std;
struct node{
	double st,ed;//线段起始位置和结束位置 
}a[15005];
bool cmp(node a,node b)
{
	return a.st < b.st;
}
void f()
{
	int n,l,w;
	cin >> n >> l >> w;
	int k = 0;//有k个有效的喷头 
	for(int i=1;i<=n;i++)
	{
		double x,r;//位置、半径
		cin >> x >> r;
		if(2*r<=w) continue; 
		double p = sqrt(r*r-(w/2.0)*(w/2.0));
		k++;
		a[k].st = x-p;
		a[k].ed = x+p; 
	}
	sort(a+1,a+1+k,cmp);//按照起始位置从小到大排序 
	double last = 0;//上一个喷头的结束
	int idx = 1;//当前喷头编号 
	int res = 0;
	while(last<l&&idx<=k) 
	{
		double max_last;//结束部分的最大值 
		bool flag = 0;//
		while( a[idx].st <= last && idx <= k )
		{
			if( flag==0 || ( flag==1 && max_last<a[idx].ed ) )
			{
				max_last = a[idx].ed;
				flag = 1;	
			}
			idx++;	
		} 
		if(!flag)
		{
			cout << -1 << endl;
			return ;
		}
		else
		{
			res++;
			last = max_last;	
		}
		
	}
	if(last>=l) cout << res << endl;
	else cout << -1 << endl;
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		f();
	}
	return 0;
}

题目

认领作业后才可以查看作业内容。
状态
正在进行…
题目
3
开始时间
2024-6-1 0:00
截止时间
2024-10-31 23:59
可延期
24 小时