首先特判 \(a_i = 0\)，然后：
\(\begin{aligned} f_k(x) & = \sum\limits_{i = 1}^k |a_i x + b_i| \\ & = \sum\limits_{i = 1}^k a_i |x + \frac{b_i}{a_i}| \end{aligned}\)
默认 \(a_i > 0\)，若不满足则 \(a_i, b_i\) 同时取相反数即可。
然后这个东西就变成了，数轴上 \(-\frac{b_i}{a_i}\) 位置上有 \(a_i\) 个点，找一个点使这个点到所有点的距离最小。
根据小学奥数，取所有 \(-\frac{b_i}{a_i}\) 的中位数（设为 \(p\)）最优。然后把 \(p\) 代入上面式子，拆绝对值即可。
使用树状数组求中位数和维护 \(\sum a_i, \sum b_i\)，复杂度 \(O(n \log n)\)。
code
// Problem: P5381 [THUPC2019] 不等式
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5381
// Memory Limit: 500 MB
// Time Limit: 3000 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;
struct frac {
ll x, y;
frac(ll a = 0, ll b = 1) {
if (b < 0) {
a = -a;
b = -b;
}
x = a;
y = b;
}
};
inline bool operator < (const frac &a, const frac &b) {
return a.x * b.y < a.y * b.x;
}
inline bool operator == (const frac &a, const frac &b) {
return a.x * b.y == a.y * b.x;
}
const int maxn = 500100;
ll n, tot;
frac lsh[maxn];
struct node {
ll a, b;
} a[maxn];
struct BIT {
ll c[maxn];
inline void update(int x, ll d) {
for (int i = x; i <= tot; i += (i & (-i))) {
c[i] += d;
}
}
inline ll query(int x) {
ll res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline int kth(ll k) {
ll s = 0;
int p = 0;
for (int i = 18; ~i; --i) {
if (p + (1 << i) <= tot && s + c[p + (1 << i)] < k) {
s += c[p + (1 << i)];
p += (1 << i);
}
}
return p + 1;
}
} t1, t2;
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i].a);
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i].b);
if (a[i].a < 0) {
a[i].a = -a[i].a;
a[i].b = -a[i].b;
}
if (a[i].a) {
lsh[++tot] = frac(-a[i].b, a[i].a);
}
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
ll s = 0, r = 0;
for (int i = 1; i <= n; ++i) {
if (a[i].a) {
int k = lower_bound(lsh + 1, lsh + tot + 1, frac(-a[i].b, a[i].a)) - lsh;
t1.update(k, a[i].a);
t2.update(k, a[i].b);
} else {
r += abs(a[i].b);
}
s += a[i].a;
int t = t1.kth((s + 1) / 2);
frac p = lsh[t];
db res = t1.query(t) * (1. * p.x / p.y) + t2.query(t);
res += -(t1.query(tot) - t1.query(t)) * (1. * p.x / p.y) - (t2.query(tot) - t2.query(t));
printf("%.6lf\n", res + r);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}