Editorial for Bedao Grand Contest 13 - SPEED
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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); }
Comments
This comment is hidden due to too much negative feedback. Show it anyway.