不会。
于是三分。
枚举每一条线段，三分最优点的坐标，然后枚举每条直线计算高度即可。
时间复杂度
，其中L为整个区间的长度。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <limits>
#include <iomanip>
#include <algorithm>
const int N = 300;
const long double EPS = 1e-12;
long double x[N], y[N];
int n;
long double calc(double );
int main(void)
{
std::cin >> n;
for (int i = 0; i < n; ++i)
std::cin >> x[i];
for (int i = 0; i < n; ++i)
std::cin >> y[i];
long double ans = std::numeric_limits <long double> ::max();
for (int i = 1; i < n; ++i)
{
long double xl = x[i - 1], xr = x[i], yl = y[i - 1], yr = y[i];
while (xr - xl > EPS)
{
long double xd = (xr - xl) / 3, yd = (yr - yl) / 3;
if (calc(xl + xd) - (yl + yd) > calc(xr - xd) - (yr - yd))
{
xl += xd;
yl += yd;
}
else
{
xr -= xd;
yr -= yd;
}
}
ans = std::min(ans, calc(xl) - yl);
}
std::cout << std::setiosflags(std::ios::fixed) << std::setprecision(3) << ans << std::endl;
return 0;
}
inline long double calc(double p)
{
long double h = 0;
for (int i = 0; i < n; ++i)
h = std::max(h, y[i]);
for (int i = 1; x[i] < p && i < n; ++i)
h = std::max(h, y[i] + (y[i] - y[i - 1]) / (x[i] - x[i - 1]) * (p - x[i]));
for (int i = n - 1; x[i - 1] > p && i >= 0; --i)
h = std::max(h, y[i] + (y[i] - y[i - 1]) / (x[i] - x[i - 1]) * (p - x[i]));
return h;
}