自动搬运

查看原文

来自洛谷，原作者为

	dormantbs **

搬运于2025-08-24 21:46:36，当前版本为作者最后更新于2018-03-02 10:29:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题乍一看挺复杂的,其实思路理清之后还是比较简单的吧。

首先我们可以手玩几组数据,发现取到最优解总是在每一段的速度都比较平均的情况下取到,因此我们不妨大胆猜想：
最优解在速度基本相同的情况下最优。

大概的证明如下(转自http://blog.163.com/bill125_zjh/blog/static/231801006201441025744282/):

反正我是看不懂QwQ,但是我们学的是OI不是数学,所以我们只要有猜想就好了对吧(雾

好的那么有了这两个个性质后,我们再继续观察题目中的耗油量的表达式:

其中$a$,$b$,$s$ 都是定值,那么这个表达式我们就可以看做$k*x+b$ 的形式,即耗油量与速度成正比。

结合以上,我们可以二分整段速度的最大值,再由这个速度计算出最优解就好了。

计算这里还有一个细节,若 $a*v+b*s \le 0$,由题意这个时候的耗油量一定是$0$。
但这个时候显然速度是可以更大的,

由$$ av+bs=0 $$

这个时候 $min\{-\frac{b*s}{a},maxv\}$ 才是更优的速度。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-15;
const int N=10010;
struct Node{
	double x,y,k,len;
	inline void init(){
		scanf("%lf%lf",&x,&y);
		k=y/x,x/=1000.0,y/=1000.0,
		len=sqrt(x*x+y*y); 
	}
}c[N];
int T,n;
double a,b,mxv,f;
inline bool ck(double mid){
	double res=0.0;
	for(int i=1;i<=n;++i){
		res+=max(a*mid+b*c[i].k,0.0)*c[i].len;
		if(res+eps>=f) return 0;
	}return 1;
}
inline double calc(double v){
	double res=0.0;
	for(int i=1;i<=n;++i){
		double tmp=a*v+c[i].k*b;
		if(tmp<=eps){
			double vv=(-b*c[i].k)/a;
			vv=min(vv,mxv);
			res+=c[i].len/vv;
		}else{
			if(v<=eps) return 0;
			res+=c[i].len/v;
		}
	}
	return res;
}
inline void sol(){
	double l=0,r=mxv,mid;
	int t=0;
	while(t<1000){
		mid=(l+r)/2;
		if(ck(mid)) l=mid;
		else r=mid;
		++t;
	} 
	double res=calc(l);
	if(res<=eps) puts("IMPOSSIBLE");
	else printf("%.5lf\n",res);
}
int main(){
	if(fopen("test.in","r")){
		freopen("test.in","r",stdin);
		freopen("test.out","w",stdout);
	}
	scanf("%d",&T);
	while(T--){
		scanf("%lf%lf%lf%lf%d",&a,&b,&mxv,&f,&n);
		for(int i=1;i<=n;++i) c[i].init();
		sol();
	}
}