NC20092. [HNOI2011]赛车游戏
描述
著名歌手LAALA最近迷上了一款赛车游戏，游戏中开车的玩家在不同的路段需要选择不同的速度，使得自己在最短的时间内到达终点。开始游戏时，车内的初始油量为f，所以游戏的关键是如何在速度和耗油量之间实现平衡。
LAALA 经过一段时间的研究后，发现这款游戏可以用一个简单的数学模型来描述，具体来说：从起点到终点的路线可以被简化成折线段，每条线段代表一个上坡或者下坡，若在一段斜率为 s(s>0 代表上坡，s=0 代表平地，s<0 代表下坡)的道路上以速度 v km/h 行驶，则每公里的耗油量为 max(0,av+bs)，其中 a 和 b 为游戏的内置参数，分别表示在平地行驶时的耗油率及斜坡对耗油量的影响(b 恒为正)。这里假设，加速和减速不耗油，且看成是瞬间完成的，所以即使在同一条线段上也可采取以不同的速度行驶的策略来缩短耗费的时间。
由于 LAALA 在以前的游戏中表现不佳，现在使用的车型依然是系统初始分配的，所以它的速度不能超过 vmax km/h。在获得这些参数后，LAALA 想知道在初始油量受限的情况下（中途不许加油）自己能得到的最佳成绩是多少。作为 LAALA 的歌迷，你能帮帮他吗?
输入描述
从文件input.txt中读入数据，输入文件的第一行是一个正整数T，表示数据组数。对每组数据，第一行是用空格隔开的4个浮点数a、b、vmax和f，其中a、b和vmax的意义如前所述，f表示初始油量，其单位也与前面的描述保持一致。第二行是一个正整数r，表示线段的数目。接下来的r行，每行是用空格隔开的2个浮点数xi和yi，分别表示在标准笛卡耳坐标系下该线段在水平方向和垂直方向的改变量(单位为米)。
输出描述
输出文件 output.txt 包含 T 行，依次对应输入中的 T 组数据。
对某组数据，若基于初始油量无法到达终点，则对应行输出 IMPOSSIBLE，否则输出最少需要的时间(单位为小时)。
示例1
输入:
3 10.0 1.0 150 0.0 1 100.0 -100.0 10.0 100.0 150 1.0 2 100 0 100 100 0.5 0.1 100 10 3 1000 0 100 10 100 -10
输出:
1.41421 IMPOSSIBLE 0.07212
C++(clang++ 11.0.1) 解法, 执行用时: 93ms, 内存消耗: 720K, 提交时间: 2022-08-29 22:37:24
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
inline int read(){
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
inline void write(int x){
static char cnt,num[15];cnt=0;
if (!x){
putchar('0');
return;
}
for (;x;x/=10) num[++cnt]=x%10;
for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=1e4+100;
int T,n;
const double eps=1e-15;
double a,b,vmax,f;
double x[maxn],y[maxn],k[maxn],len[maxn];
double Abs(double x){
if (x<0) return -x;
return x;
}
bool check(double x){
double s=0;
for (int i=1;i<=n;i++){
s+=len[i]*max(0.0,a*x+k[i]*b);
if (s-eps>=f) return false;
}
return true;
}
double calc(double x){
double s=0.0,tmp;
if (x<=eps) return 0;
for (int i=1;i<=n;i++){
tmp=a*x+k[i]*b;
if (tmp<=eps) s+=len[i]/min(vmax,(-b*k[i]/a));
else s+=len[i]/x;
}
return s;
}
void work(){
double l=0,r=vmax,mid;
int id=0;
while (id<1000){
mid=(l+r)/2;
if (check(mid)) l=mid; else r=mid;
id++;
}
r=calc(l);
if (r<=eps){
printf("IMPOSSIBLE\n");
return;
}
printf("%.5f\n",r);
}
int main(){
#ifdef ylx
freopen("p3218.in","r",stdin);
freopen("p3218.out","w",stdout);
#endif
T=read();
while (T--){
scanf("%lf%lf%lf%lf",&a,&b,&vmax,&f);
n=read();
for (int i=1;i<=n;i++){
scanf("%lf%lf",&x[i],&y[i]);
k[i]=y[i]/x[i];
x[i]/=1000.0;y[i]/=1000.0;
len[i]=sqrt(x[i]*x[i]+y[i]*y[i]);
}
work();
}
return 0;
}