Subtask 1: ~n=2~

Ta thấy ~A~ nằm ở vùng 1 và ~B~ nằm ở vùng 2, ta chặt tam phân vị trí cắt của con đường lên ~a_1~.

Subtask 2:

Ta có Định Luật Snell: ~\displaystyle\frac{\sin\theta_1}{\sin\theta_2} = \frac{v_1}{v_2}~

Nhận xét: thời gian ngắn nhất luôn bằng với thời gian 1 tia sáng đi từ ~A~ đến ~B~, góc khúc xạ của tia sáng giữa 2 môi trường khác nhau tính bằng Định Luật Snell. Ta chặt nhị phân tìm góc xuất phát từ điểm ~A~ sao cho từ góc đó ta đi đến được điểm ~B~ bằng Định Luật Snell.

Code mẫu

#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define fid(i,a,b) for(int i=a;i>=b;i--)
#define getbit(x,i) ((x>>i)&1)
#define pii pair<int,int>
#define ll long long
#define TunaNgoo "g13e"
#define maxn 100005
using namespace std;
int n, a[maxn], v[maxn], x_1, y_1, x_2, y_2;
int L, R;
long double dist(long double x, long double y, long double u, long double v) {
    long double sum = 0;
    sum += (x - u) * (x - u);
    sum += (y - v) * (y - v);
    return sqrt(sum);
}

long double calc(long double sina, long double r) {
    long double tmp = 1;
    tmp /= sina * sina;
    tmp -= 1;
    tmp = sqrt(tmp);
    tmp = r / tmp;
    return tmp;
}

bool check(long double sina) {
    long double y = y_1;
    y += calc(sina, a[L] - x_1);
    fi(i, L, R) {
        sina = (long double) v[i + 1] * sina / v[i];
        if(sina >= 1) return true;
        y += calc(sina, min(a[i + 1], x_2) - a[i]);
        if(y >= y_2) return true;
    }
    if(y >= y_2) return true; else return false;
}

long double calcTime(long double sina) {
    long double time = 0;
    long double y = y_1;
    y += calc(sina, a[L] - x_1);
    time += (calc(sina, a[L] - x_1) / sina) / v[L];

    fi(i, L, R) {
        sina = (long double) v[i + 1] * sina / v[i];
        y += calc(sina, min(a[i + 1], x_2) - a[i]);
        time += (calc(sina, min(a[i + 1], x_2) - a[i]) / sina) / v[i + 1];
    }
    return time;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if(fopen(TunaNgoo".inp", "r")) {
        freopen(TunaNgoo".inp", "r", stdin);
        freopen(TunaNgoo".out", "w", stdout);
    }
    cin >> n;
    fi(i, 0, n) cin >> a[i];
    fi(i, 1, n) cin >> v[i];
    cin >> x_1 >> y_1 >> x_2 >> y_2;

    if(x_1 > x_2) {
        swap(x_1, x_2);
    }
    if(y_1 > y_2) {
        swap(y_1, y_2);
    }
    fi(i, 1, n) {
        if(a[i] > x_1) {
            L = i;
            break;
        }
    }
    fid(i, n, 1) {
        if(a[i] < x_2) {
            R = i;
            break;
        }
    }

    if(L > R) {
        cout << fixed << setprecision(7) << dist(x_1, y_1, x_2, y_2) / v[L];
        return 0;
    }

    if(y_1 == y_2) {
        long double ans = 0;
        fi(i, L - 1, R) {
            ans += (long double) (min(a[i + 1] , x_2) - max(a[i], x_1)) / v[i + 1];
        }
        cout << fixed << setprecision(7) << ans;
        return 0;
    }

    long double l = 0, r = 1;
    fi(loop, 1, 100) {
        long double m = (l + r) / 2;
        if(check(m)) r = m; else l = m;
    }

    cout << fixed << setprecision(7) << calcTime(l);
}