P5381 [THUPC 2019] Inequalities

> Time goes back to June 7, 2017. In the afternoon, the sunlight is just right. > > You, in the examination room, keep writing without stopping. Amid the rustling sounds, you fill in an answer sheet meant for your past and future selves. > > Just like you have practiced countless times, you jump straight to the last big problem on this math paper. For the either-or question, you directly choose the latter. After quickly skimming the statement, your furrowed brows gradually relax. > > “This is in the bag.” > > You do not dare to pause for even a moment, and you move one small step closer to your dream. Given two $n$-dimensional real vectors $\vec{a}=(a_1,a_2,\dots,a_n)$ and $\vec{b}=(b_1,b_2,\dots,b_n)$, define $n$ functions $f_1,f_2,\dots,f_n$ with domain $\mathbb{R}$: $$f_k(x)=\sum_{i=1}^{k} \lvert a_ix+b_i\rvert \quad (k=1,2,\dots,n)$$ Now, for each $k=1,2,\dots,n$, find the minimum value of $f_k$ over $\mathbb{R}$. It can be proven that the minimum always exists.

The first line contains an integer $n$, representing the length of the vectors and the number of functions. The next two lines each contain $n$ integers, describing the components of vectors $\vec{a}$ and $\vec{b}$, separated by spaces. For all input data, it holds that $1\le n\le 5\times 10^5$ and $\lvert a_i\rvert ,\lvert b_i\rvert

Output $n$ lines. The $i$-th line ($i=1,2,\dots,n$) contains a real number, representing the minimum value of $f_i$ over $\mathbb{R}$. Your output will be considered correct if the absolute error or relative error compared with the standard answer is less than $10^{-6}$.

### Sample Explanation $f_1(x)=\lvert x+1\rvert$, which obviously achieves its minimum value $0$ at $x=-1$. $f_2(x)=\lvert x+1\rvert +\lvert x+2\rvert$. It can be proven that it achieves its minimum value $1$ at any point in $[-2,-1]$. ##### Postscript Later, the students who took the third national exam paper once again recalled the fear of being dominated by parametric equations. ##### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019. Resources such as solutions can be found at . Translated by ChatGPT 5