TIOJ 2240：蛋餅騎車車

TIOJ 2240：蛋餅騎車車

題目大意：你在座標 $(0,0)$，想到達 $(X, Y)$，有 $n+1$ 個分界點 $x = a_0\sim a_n$，$x = a_{i-1}\sim a_i$ 的速度是 $v_i$，想問最少可以用多少時間到達目的地。

解法：在寫程式時竟然會用到物理定律，可以由司乃耳定律知道 $\frac{v_1}{sin(θ_1)} = \frac{v_2}{sin(θ_2)}$，如果按照式子折射，波行進的時間會最短，所以可以對速度最快的區域固定一個角度射出 (這樣就不用擔心全反射)，然後看最後到達的 $y$ 座標是 $>$ 還是 $≤Y$，也就是要二分搜的意思。

只是這樣子只能拿到前三組測資，原因是有可能當角度只動一點點時，位移卻增加很多，在看了官解後，才知道不能對 $θ$ 二分搜，要對 $tan(θ)$ 二分搜，證明有寫在官解裡。實作出來後，還是 $\text{WA}$ 了好幾十筆才過，然後我讓程式跑 $4600$ 毫秒就停止。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define double long double
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;
const int times = 200;
const double start = clock();

int n, x, y, mx;
int a[SIZE], v[SIZE];

void solve() {
    cin >> x >> y >> n;
    FOR (i, 0, n) cin >> a[i];
    for (int i = n; i >= 1; i--) a[i] -= a[i - 1];
    FOR (i, 1, n) cin >> v[i], mx = max (mx, v[i]);
    double l = (double) y / x, r = 1e9;
    while (clock() - start <= 4.6 * CLOCKS_PER_SEC) {
        double mid = (l + r) / 2, tot = 0;
        bool ok = 1;
        FOR (i, 1, n) {
            tot += mid * a[i] * v[i] / sqrt (mid * mid * (1ll * mx * mx - 1ll * v[i] * v[i]) + 1ll * mx * mx);
            if (tot > y) {ok = 0; break;}
        }
        if (ok) l = mid;
        else r = mid;
    }
    double ans = 0;
    FOR (i, 1, n) ans += sqrt ((l * l + 1)) * a[i] * mx / (v[i] * sqrt (l * l * (1ll * mx * mx - 1ll * v[i] * v[i]) + 1ll * mx * mx));
    cout << fixed << setprecision (20) << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！