还是很有趣的一道题。场上直接暴拆式子，要维护动态凸包，本来以为是 \(\log^2\) 的，写着写着发现是 \(\log^3\)，遂弃。
显然梯形面积最小等价于 \(y_0 + y_1\) 最小，而 \(y_0 + y_1\) 最小等价于梯形在 \(m = \frac{n}{2}\) 处最小。
把上凸包建出来，发现过 \(x = m\) 的线段，所在直线在 \(x = m\) 处最小。
又因为过 \(x = m\) 的线段 \(x_1 = l, x_2 = r\) 一定满足 \(l \le m < r\)，所以即等价于求 \(\forall l \le m < r, (l, a_l), (r, a_r)\) 在 \(x = m\) 处的最大值。
于是我们砍半，对于 \([0, m]\) 的询问，我们把 \(a\) 在 \([m + 1, n]\) 的上凸包建出来，然后对于一个询问 \(i\)，我们可以二分然后取前缀 \(\max\) 处理出 \([0, i]\) 的 \(b\) 的点和上凸包的点构成的线段在 \(x = m\) 的最大值，和 \([i + 1, m]\) 的 \(a\) 的点和上凸包的点构成的线段在 \(x = m\) 的最大值。
对于 \([m + 1, n]\) 的询问类似。
所以总时间复杂度就是 \(O(n \log n)\)。
code
// Problem: F. Landscaping
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1901/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, a[maxn], b[maxn], m;
ldb f[maxn], g[maxn];
struct node {
ldb x, y;
node(ldb a = 0, ldb b = 0) : x(a), y(b) {}
} p[maxn];
int stk[maxn], top;
inline node operator - (const node &a, const node &b) {
return node(a.x - b.x, a.y - b.y);
}
inline ldb operator * (const node &a, const node &b) {
return a.x * b.y - a.y * b.x;
}
inline ldb calc(node a, node b) {
ldb k = (a.y - b.y) / (a.x - b.x);
ldb t = a.y - a.x * k;
return k * n / 2 + t;
}
inline ldb calc(node x) {
int l = 1, r = top;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (calc(x, p[stk[mid]]) < calc(x, p[stk[mid + 1]])) {
l = mid + 1;
} else {
r = mid;
}
}
ldb ans = -1e18;
for (int i = l; i <= r; ++i) {
ans = max(ans, calc(x, p[stk[i]]));
}
return ans;
}
void solve() {
scanf("%lld", &n);
--n;
m = n / 2;
for (int i = 0; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 0; i <= n; ++i) {
scanf("%lld", &b[i]);
}
for (int i = m + 1; i <= n; ++i) {
p[i] = node(i, a[i]);
while (top >= 2 && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top - 1]]) >= 0) {
--top;
}
stk[++top] = i;
}
g[m + 1] = -1e18;
for (int i = 0; i <= m; ++i) {
f[i] = max(i ? f[i - 1] : -1e18, calc(node(i, b[i])));
}
for (int i = m; i; --i) {
g[i] = max(g[i + 1], calc(node(i, a[i])));
}
for (int i = 0; i <= m; ++i) {
printf("%.12Lf ", max(f[i], g[i + 1]) * 2);
}
top = 0;
for (int i = 0; i <= m; ++i) {
p[i] = node(i, b[i]);
while (top >= 2 && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top - 1]]) >= 0) {
--top;
}
stk[++top] = i;
}
f[m] = g[n + 1] = -1e18;
for (int i = m + 1; i <= n; ++i) {
f[i] = max(f[i - 1], calc(node(i, b[i])));
}
for (int i = n; i > m; --i) {
g[i] = max(g[i + 1], calc(node(i, a[i])));
}
for (int i = m + 1; i <= n; ++i) {
printf("%.12Lf ", max(f[i], g[i + 1]) * 2);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}