Landscaping
Contest: Educational Codeforces Round 158 (Rated for Div. 2)
Difficulty rating: 2900
Tags: binary search, geometry, two pointers

You are appointed to a very important task: you are in charge of flattening one specific road.

The road can be represented as a polygonal line starting at $$$(0, 0)$$$, ending at $$$(n - 1, 0)$$$ and consisting of $$$n$$$ vertices (including starting and ending points). The coordinates of the $$$i$$$-th vertex of the polyline are $$$(i, a_i)$$$.

"Flattening" road is equivalent to choosing some line segment from $$$(0, y_0)$$$ to $$$(n - 1, y_1)$$$ such that all points of the polyline are below the chosen segment (or on the same height). Values $$$y_0$$$ and $$$y_1$$$ may be real.

You can imagine that the road has some dips and pits, and you start pouring pavement onto it until you make the road flat. Points $$$0$$$ and $$$n - 1$$$ have infinitely high walls, so pavement doesn't fall out of segment $$$[0, n - 1]$$$.

The cost of flattening the road is equal to the area between the chosen segment and the polyline. You want to minimize the cost, that's why the flattened road is not necessary horizontal.

But there is a problem: your data may be too old, so you sent a person to measure new heights. The person goes from $$$0$$$ to $$$n - 1$$$ and sends you new heights $$$b_i$$$ of each vertex $$$i$$$ of the polyline.

Since measuring new heights may take a while, and you don't know when you'll be asked, calculate the minimum cost (and corresponding $$$y_0$$$ and $$$y_1$$$) to flatten the road after each new height $$$b_i$$$ you get.

Input format:
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the polyline.

The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$0 \le a_i \le 10^9$$$; $$$a_0 = a_{n - 1} = 0$$$) — the heights of the corresponding vertices.

The third line contains $$$n$$$ integers $$$b_0, b_1, \dots, b_{n - 1}$$$ ($$$0 \le b_i \le 10^9$$$; $$$b_0 = b_{n - 1} = 0$$$) — the new heights of the corresponding vertices.

Output format:
Print $$$n$$$ numbers: as the $$$i$$$-th number ($$$0$$$-indexed) print $$$y_0 + y_1$$$ of the "best segment" (i. e. the sum of coordinates of the segment that gives the minimum cost) if you already know actual heights $$$b_0, \dots, b_i$$$.

If there are several "best segments", print the minimum possible $$$y_0 + y_1$$$ among them.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer is accepted if and only if $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first answer in the first example is shown on the picture above.

You can achieve the second answer with the following "best segment":

You can achieve the third answer using the following "best segment":

You can achieve the fourth answer with the "best segment" shown below:

Example input:
5
0 5 1 3 0
0 1 3 2 0

Example output:
8.000000000000 4.000000000000 6.000000000000 6.000000000000 6.000000000000

Example input:
6
0 4 1 3 3 0
0 1 4 0 1 0

Example output:
7.000000000000 5.000000000000 7.500000000000 7.500000000000 6.666666666667 6.666666666667

Editorial:
Let's say that we are searching for the best line that contains the best segment.
Observation $$$1$$$: the best line touches at least one vertex of the polyline. Otherwise, you can push it down until it touches polyline.
Observation $$$2$$$: the best line touches two vertices of the polyline. Suppose it touches only one vertex $$$i$$$ then it's not hard to prove that rotating the line around point $$$i$$$ either clockwise or counterclockwise will decrease the area under the line.
Observation $$$3$$$: if both points are on the left half ($$$i < j < \frac{n}{2}$$$) then rotating the line clockwise around point $$$j$$$ will decrease the area. Analogically, if both points are on the right half ($$$\frac{n}{2} < i < j$$$) then rotating the line counterclockwise around $$$i$$$ will decrease the area.
Observation $$$4$$$: since all points of the polyline should be under the line, then the vertices the line touches are the consecutive vertices on the convex hull of the polyline.
In total, we understand that the pair of points we need forms a segment of the convex hull that crosses a vertical line $$$x = \frac{n}{2}$$$.
Knowing that, what can we do? Let's split all vertices in two halves: "left half" with all vertices to the left of $$$\frac{n}{2}$$$ and "right half" with all vertices to the right. Note that while we process the first half of "queries" the right half (vertices in $$$[\frac{n}{2}, n - 1]$$$) remains the same. If we know how to process the first half of queries, then processing the second half is practically the same thing but in the reverse order.
So, how to find that best segment of the convex hull that crosses $$$x = \frac{n}{2}$$$ efficiently while we work with the left half of vertices? Note that if we look at all segments that connect vertex from the left part with vertex from the right part:
1. each segment will certainly cross $$$x = \frac{n}{2}$$$ in some real point $$$y_c$$$;
2. the segment of the convex hull will have maximum possible $$$y_c$$$ (otherwise, it's not a convex hull segment).
There are around $$$n^2$$$ segment that crosses $$$\frac{n}{2}$$$ but we don't need all of them. Let's calculate for each vertex $$$i$$$ ($$$i < \frac{n}{2}$$$) (both the old and new values) the segment that crosses $$$\frac{n}{2}$$$ and has $$$y_c$$$ maximum possible.
Note that this "maximum possible" segment connects $$$i$$$ with some vertex $$$j$$$ that has to be on the convex hull that was built on the right half (otherwise, we will find convex hull point with higher slope and its $$$y_c$$$ will be bigger).
In other words, for each point from the left, we are searching a tangent line to the convex hull on the right. And we can do it efficiently with binary search while checking some cross products. Let's name that tangent line as $$$t(x, y)$$$ where $$$(x, y)$$$ is a point from the left half.
One more observation: $$$y_c = \frac{y_0 + y_1}{2}$$$. You can prove it by looking at the area of trapezoid that formed by segment $$$(0, y_0) - (n - 1, y_1)$$$. So, let's define a function $$$f(l)$$$ that takes line $$$l$$$ and returns $$$2 y_c$$$ (or the answer to the task).
We have all we need to calculate the answer: the answer to the $$$i$$$-th query is equal to the maximum among $$$f(t(j, b_j))$$$ for all $$$j \le i$$$ and $$$f(t(j, a_j))$$$ for all $$$i < j < \frac{n}{2}$$$.
In total, the solution is next:
1. build convex hull on vertices $$$[\frac{n}{2}, n - 1]$$$;
2. calculate $$$t(i, a_i)$$$ with binary search for all $$$i < \frac{n}{2}$$$;
3. calculate $$$f(t(i, a_i))$$$ for all $$$i < \frac{n}{2}$$$ and store suffix maximums among these values;
4. calculate $$$t(i, b_i)$$$ with binary search for all $$$i < \frac{n}{2}$$$;
5. calculate $$$f(t(i, b_i))$$$ for all $$$i < \frac{n}{2}$$$ and store prefix maximums among these values;
6. calculate the $$$i$$$-th answer as maximum between the $$$i$$$-th prefix maximum and the $$$(i+1)$$$-th suffix maximum.
In order to solve the task for the right half $$$[\frac{n}{2}, n - 1]$$$ just reverse arrays $$$a$$$ and $$$b$$$ and swap them, and do the same algorithm above. It's true, because replacing first $$$k$$$ values $$$a_i$$$ with $$$b_i$$$ in array $$$a$$$ is equivalent to replacing last $$$n - k$$$ values $$$b_i$$$ with $$$a_i$$$ in array $$$b$$$.
Complexity of the solution is $$$O(n \log n)$$$ because of binary searches. Note that we can do everything in integers, except calculating the values of function $$$f$$$ and taking maximum among $$$f$$$.