BZOJ3695 滑行

题意

一个矩形的地面被划分成不同的 $N$ 块,每块的高度为 $H[i]$ ,每块的长度都为 $X$ ,现在有一个滑块,给出在每个块上的限速$V[i]$ ,求从右上角到左下角最短时间是多少

题解

这题在 miskcoo的博客上看到的,感觉挺神奇的
用到两个物理定理来解决这题
1. 光的最速原理:光从一点射到另一点,用的路径一定是所有路径中最短的
2. 折射定律:光的入射角 $\theta_1$ 和折射角 $\theta_2$ 与光在两块介质中的速度 $v_1$, $v_2$ 有如下关系:
$$ \frac{\sin \theta_1}{v_1}=\frac{\sin\theta_2}{v_2} $$

然后将滑块看作光,就可以用这两个定理来解题
至于数学推导,不讲了,在链接里有
然后就没什么好讲的了又水了一篇

代码

#define reg register
#define MAX_N 107
typedef long long ll;

int N;
double X, h[MAX_N], v[MAX_N];

inline void input () {
    read(N), read(X);
    for (int i = 1; i <= N; ++i)
        read(h[i]);
    for (int i = 1; i <= N; ++i)
        read(v[i]);
}

inline double check (double sina) {
    double dist = 0, tana;
    for (int i = 1; i <= N; ++i) {
        tana = sina / sqrt(1.0 - sina * sina);
        dist += h[i] * tana;
        if (i != N) sina = sina / v[i] * v[i + 1];
        if (sina > 1.0) return X + 1;
    }
    return dist;
}

inline double calc (double sina) {
    double tm = 0, cosa;
    for (int i = 1; i <= N; ++i) {
        cosa = sqrt(1.0 - sina * sina);
        tm += h[i] / (v[i] * cosa);
        if (i != N) sina = sina / v[i] * v[i + 1];
    }
    return tm;
}

inline void solve () {
    double l = 0.0, r = 1.0, mid, ans = -1;
    for (int i = 1; i <= 1000; ++i) {
        mid = (l + r) * 0.5;
        if (check(mid) >= X)
            r = mid, ans = mid;
        else l = mid;
    }
    printf("%.3lf\n", calc(ans));
}

int main () {
    input();
    solve();
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注