120565C

https://ac.nowcoder.com/acm/contest/120565/C

显然二分答案。

主要是全覆盖，那么圆的有效面积高度一定要达到，那么就是：能否选出条高度达到的线段使它们覆盖轴的。做一个简单贪心即可。

贪心：在所有左端点小于当前的线段中选出右端点最大的更新，同时线段计数，得到最少全覆盖所需的线段数；二分时判断最终是否能全覆盖，最少线段数是否。

#include<bits/stdc++.h>
using namespace std;
int n,k;
double h,c,h2;
const double eps=1e-10,inf=1.8e6;
struct o{
	double p,v;
}a[1000100];
struct oo{
	double l,r;
	bool operator <(const oo d) const{
		return l-d.l<eps;
	}
}b[1000100];
double pf(double x){return 1.0*x*x;}
int pd(double t){
	int tot=0;
	for(long long i=1;i<=n;i++){
		double r=1.0*a[i].v*t;
		if(r<h+eps) continue;
		double len=1.0*sqrt(pf(r)-h2);
		b[++tot].l=-len+a[i].p;
		b[tot].r=len+a[i].p;
	}
	sort(b+1,b+1+tot);
	int i=0,cnt=0;
	double nowr=0;
	while(i+1<=tot&&nowr<c+eps){
		double lenr=0;
		while(i+1<=tot&&b[i+1].l<nowr+eps){
			lenr=max(lenr,b[++i].r);
		}
		if(lenr<nowr+eps) break;
		nowr=lenr; 
		cnt++;
	}
	if(nowr-c<=eps) return 0;
	return cnt<=k;
}
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main(){
	n=read();k=read();h=1.0*read();c=1.0*read();
	h2=pf(h);
	for(int i=1;i<=n;i++){
		a[i].p=1.0*read();a[i].v=1.0*read();
	}
	double l=0,r=inf;
	while(r-l>1e-5){
		double mid=(l+r)/2.0;
		if(pd(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	printf("%.10lf",l);
	return 0;
}