M_sea

洛谷3218 [HNOI2011]赛车游戏
LuoguBZOJ分析这题竟然卡精度......发现每一段的速度都比较平均的时候是最优的。证明当然不会啦。于是二分...
扫描右侧二维码阅读全文
31
2019/01

洛谷3218 [HNOI2011]赛车游戏

Luogu

BZOJ

分析

这题竟然卡精度......

发现每一段的速度都比较平均的时候是最优的。

证明当然不会啦。

于是二分这个速度,然后直接计算就行了。

一个小细节:

如果$a\cdot v+b\cdot s$leq 0$,这时的耗油量显然是$0$,但是速度可以更快。

于是这一段的速度应该是$\min\left\{vmax,-\frac{b\cdot s}{a}\right\}$

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define sqr(x) ((x)*(x))
#define re register
using namespace std;

const int N=10000+10;
const double EPS=1e-15;

int n;
double a,b,vmax,f;
struct Road { double x,y,k,l; } r[N];

inline int check(double mid) {
    double sum=0;
    for (re int i=1;i<=n;++i) {
        sum+=max(a*mid+b*r[i].k,0.0)*r[i].l;
        if (sum+EPS>=f) return 0;  
    }
    return 1;
}

inline void solve() {
    double L=0,R=vmax; int T=0;
    while (T<=1000) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
        ++T;
    }
    double ans=0,v=L;
    for (re int i=1;i<=n;++i) {
        if (a*v+b*r[i].k<=EPS) ans+=r[i].l/min(vmax,-b*r[i].k/a); //上面说的细节
        else {
            if (v<=EPS) { puts("IMPOSSIBLE"); return; } //这个要写里面...
            ans+=r[i].l/v;
        }
    }
    if (ans<=EPS) puts("IMPOSSIBLE");
    else printf("%.5lf\n",ans);
}

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%lf%lf%lf%lf",&a,&b,&vmax,&f);
        scanf("%d",&n);
        for (re int i=1;i<=n;++i) {
            scanf("%lf%lf",&r[i].x,&r[i].y);
            r[i].x/=1000,r[i].y/=1000;
            r[i].k=r[i].y/r[i].x,r[i].l=sqrt(sqr(r[i].x)+sqr(r[i].y));
        }
        solve();
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 13 PM

发表评论