# 2. 题解 A: 自适应暴力

“折” 的地方肯定是在此线段与区域交界线的交点处，上下移动该交点就能 “折” 这根线。

（当然点 $D$也可能需要移动，但是我们最好不要移动它，因为移动它可能会导致来回修改点 $E$、点 $D$的位置，复杂度很高，还不如等以后随机到点 $D$的后面的点的位置来更新它）

#include <bits/stdc++.h>

#define NS (105)
#define REG register
#define eps (3e-4)

using namespace std;

int n, C = 450000; // 随机次数

double d[NS], f[NS], Y, fx[NS], ans, tot;

inline double str(REG double x, REG double y) // string，弦长
{
return sqrt(x * x + y * y);
}

inline double fmn(REG int a) // 三分法找函数极值
{
REG double l = fx[a - 1], r = fx[a + 1], mid, fl, fr;
while (r - l > eps * 2)
{
mid = (l + r) * 0.5;
fl = str(d[a], mid - eps - fx[a - 1]) * f[a];
fl += str(d[a + 1], fx[a + 1] - mid + eps) * f[a + 1];
fr = str(d[a], mid + eps - fx[a - 1]) * f[a];
fr += str(d[a + 1], fx[a + 1] - mid - eps) * f[a + 1];
if (fl < fr) r = mid; else l = mid;
}
return (l + r) * 0.5;
}

double tmp;

void fix(REG int a)
{
if (--C <= 0) return;
tmp = fx[a], fx[a] = fmn(a);
if (abs(tmp - fx[a]) > eps && a > 1) fix(a - 1);
}

int main(int argc, char const* argv[])
{
scanf("%d%lf", &n, &Y), srand(n * 233);
for (REG int i = 1; i <= n; i += 1) scanf("%lf", &d[i]), tot += d[i];
for (REG int i = 1; i <= n; i += 1) scanf("%lf", &f[i]), f[i] = 1 / f[i];
for (REG int i = 1; i <= n; i += 1) tmp += d[i], fx[i] = tmp * Y / tot;
while (C > 0 && n > 1) fix(rand() % (n - 1) + 1);
for (REG int i = 1; i <= n; i += 1)
ans += str(d[i], fx[i] - fx[i - 1]) * f[i];
printf("%.3f\n", ans);
return 0;
}


# 题解 B: 费马光程原理

$$\frac {sin \alpha} {V _ \alpha} = \frac {sin \beta} {V _ \beta}$$

#include <bits/stdc++.h>

#define NS (105)

using namespace std;

int n;

double X, H[NS], V[NS], ans;

inline double str(double x, double y)
{
return sqrt(x * x + y * y);
}

bool check(double s1)
{
double rem = 0;
for (int i = 1; i <= n; i += 1)
{
rem += H[i] * tan(asin(s1));
s1 = s1 / V[i] * V[i + 1];
}
return rem <= X;
}

int main(int argc, char const* argv[])
{
scanf("%d%lf", &n, &X);
for (int i = 1; i <= n; i += 1) scanf("%lf", &H[i]);
for (int i = 1; i <= n; i += 1) scanf("%lf", &V[i]);
double l = 0, r = X / str(H[1], X), mid;
for (int C = 1; C <= 100; C += 1)
{
mid = (l + r) * 0.5;
if (check(mid)) l = mid;
else r = mid;
}
l = (l + r) * 0.5;
for (int i = 1; i <= n; i += 1)
{
ans += H[i] / cos(asin(l)) / V[i];
l = l / V[i] * V[i + 1];
}
printf("%.3f\n", ans);
return 0;
}