记录编号	117629	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 赛车游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.248 s
提交时间	2014-08-30 18:53:14	内存使用	0.71 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
const double eps=1e-18,epsf=1e-7,INF=1e9;
const int SIZEN=10010;
int N;
double a,b,vmax,f;
double L[SIZEN]={0},s[SIZEN]={0};
double fd[SIZEN]={0},fe[SIZEN]={0},ft[SIZEN]={0};//每段路的最小导数,最小油耗,最长耗时
double mnd,mxd;//最小和最大的可能导数
double stt;
bool legal[SIZEN]={0};
/*
若某段路耗油E,则v=(E/L-bs)/a
t=(L^2a)/(E-bsL)
f'(t)=-L^2a/(E-bsL)^2
*/
inline double sqr(double x){return x*x;}
double e_calc_d(double E,int i){
	double ans=-L[i]*L[i]*a/((E-b*s[i]*L[i])*((E-b*s[i]*L[i])));
	return fabs(ans)>eps?ans:0;
}
double e_calc_t(double E,int i){
	double ans=L[i]*L[i]*a/(E-b*s[i]*L[i]);
	return fabs(ans)>eps?ans:0;
}
double e_calc_v(double E,int i){
	double ans=(E-b*s[i]*L[i])/(a*L[i]);
	return fabs(ans)>eps?ans:0;
}
double d_calc_e(double d,int i){
	double ans=sqrt(-L[i]*L[i]*a/d)+b*s[i]*L[i];
	return fabs(ans)>eps?ans:0;
}
void calc(double md,double &t,double &e){
	//最小导数为md,计算时间和油耗
	t=e=0;
	for(int i=1;i<=N;i++){
		if(fd[i]>=md){
			t+=ft[i];
			e+=fe[i];
			continue;
		}
		double E=d_calc_e(md,i);
		if(e_calc_v(E,i)>=vmax){
			t+=L[i]/vmax;
			e+=L[i]*(a*vmax+b*s[i]);
			continue;
		}
		t+=e_calc_t(E,i);
		e+=E;
	}
}
void work(void){
	double l=mnd,r=mxd;
	double tsum,esum;
	int cnt=0;
	while(cnt<80){
		double mid=(l+r)/2.0;
		calc(mid,tsum,esum);
		if(tsum>24.0){//跑的时间太长了,说明导数太小
			l=mid;
		}
		else if(esum>f){//耗油太多了,说明导数太大
			r=mid;
		}
		else if(esum<f){//耗油太少了,说明导数太小
			l=mid;
		}
		cnt++;
	}
	calc((l+r)/2.0,tsum,esum);
	tsum+=stt;
	if(tsum>24.0||esum>f+epsf) printf("IMPOSSIBLE\n");
	else printf("%.5lf\n",tsum);
}
void prepare(void){
	//当最小导数最小时,令所有段均跑24h或不耗油
	mnd=INF,mxd=-INF;
	stt=0;
	for(int i=1;i<=N;i++){
		if(s[i]<0&&(-s[i]*b/a)>=vmax){
			stt+=L[i]/vmax;
			legal[i]=false;
		}
		else legal[i]=true;
	}
	int tot=0;
	for(int i=1;i<=N;i++){
		if(legal[i]){
			tot++;
			L[tot]=L[i];s[tot]=s[i];
		}
	}
	N=tot;
	double E;
	for(int i=1;i<=N;i++){
		if(s[i]<0) E=0;
		else E=L[i]*(a*L[i]/24.0+b*s[i]);//跑24h的油耗
		fe[i]=E;
		fd[i]=e_calc_d(E,i);
		ft[i]=e_calc_t(E,i);
		mnd=min(mnd,fd[i]);
	}
	//当最小导数最大时,令所有段均耗掉所有油
	//这里没考虑vmax,应该没问题......
	for(int i=1;i<=N;i++){
		mxd=max(mxd,e_calc_d(f,i));
	}
}
bool able_pass(void){
	double sum=0;
	for(int i=1;i<=N;i++){
		if(s[i]>=0) sum+=b*s[i]*L[i];
	}
	if(sum>epsf&&sum>=f-epsf) return false;
	return true;
}
void read(void){
	scanf("%lf%lf%lf%lf",&a,&b,&vmax,&f);
	scanf("%d",&N);
	double x,y;
	for(int i=1;i<=N;i++){
		scanf("%lf%lf",&x,&y);
		L[i]=sqrt(x*x+y*y)/1000.0;
		s[i]=y/x;
	}
}
int main(){
	freopen("carrace.in","r",stdin);
	freopen("carrace.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		read();
		if(!able_pass()) printf("IMPOSSIBLE\n");
		else{
			prepare();
			work();
		}
	}
	return 0;
}