AT48 レースゲーム 题解

这道题 一道大概暴力能过的样子 具体思路就是向上走，然后在每个点找到能到达的倾斜角 最小 和 最大 的点 然后判断哪一个点更优 然后记录答案 然后这样一直到终点 最后的路径大概就像这样（图中红线）  然后再介绍一下hypot()函数 这个函数是算两点欧式几何距离哒 大概就和代码中的getdis()效果相同 不多说下面贴代码↓ ```cpp #include <bits/stdc++.h> using namespace std; const double dis_max = 1e17; const int maxn = 2e5 + 5; int n, s, e; int l[maxn], r[maxn]; double ans = 0; double getdis(double a, double b) { return sqrt(a * a + b * b); } void solve() { l[n] = r[n] = e; int nowy = 0; double nowx = s; while (nowy < n) { double zuoarc = -dis_max, youarc = dis_max; int ly = nowy, ry = nowy; for (int y = nowy + 1; y <= n; y++) { double larc = (l[y] - nowx) / (y - nowy), rarc = (r[y] - nowx) / (y - nowy); if (larc > zuoarc) { zuoarc = larc; ly = y; } if (rarc < youarc) { youarc = rarc; ry = y; } if (zuoarc >= youarc) { if (ly < ry) { ans += hypot/*getdis*/(l[ly] - nowx, ly - nowy); nowy = ly; nowx = l[ly]; } else { ans += hypot/*getdis*/(r[ry] - nowx, ry - nowy); nowy = ry; nowx = r[ry]; } break; } } } return; } signed main() { scanf("%d%d%d", &n, &s, &e); for (int i = 0; i <= n; i++) scanf("%d%d", &l[i], &r[i]); solve(); printf("%0.14lf", ans); return 0; } ```