Hobbits
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 2500
Tags: binary search, geometry

The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with $$$n$$$ points $$$(x_i, y_i)$$$, numbered from $$$1$$$ to $$$n$$$ ($$$x_i < x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$). Hobbits start their journey at the point $$$(x_1, y_1)$$$ and should reach the point $$$(x_n, y_n)$$$ to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point $$$(x_n, y_n)$$$ and has the height $$$H$$$, so the Eye is located at the point $$$(x_n, y_n + H)$$$. In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$H$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le H \le 10^4$$$) — the number of vertices in polyline and the tower height.

The next $$$n$$$ lines contain two integers $$$x_i, y_i$$$ each ($$$0 \le x_i \le 4 \cdot 10^5$$$; $$$0 \le y_i \le 10^4$$$) — the coordinates of the polyline vertices. It is guaranteed that $$$x_i < x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$.

Output format:
Print one real number — the total distance the hobbits have to walk while wearing cloaks. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$ — formally, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, your answer will be accepted if $$$\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Example input:
6 10
10 40
20 10
25 30
30 15
50 15
65 30

Example output:
70.4034587602

Example input:
9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5

Example output:
27.2787986124

Editorial:
Let's start with the general idea of the solution. To solve the problem, we need to iterate over all relief segments and understand, which part the segment is seen by the Eye. A segment point can be hidden from the Eye by several mountains, but it is enough to track only the highest mountain. Generally speaking, the relief segments can be processed in any order, bit it would be more convenient to iterate on them backwards — i.e. in the order from the Eye to the start point. Processing the segments in reversed order will allow to recalculate the highest mountain easier.
Let's now discuss implementation details. Formally speaking, there are $$$n$$$ relief points $$$p_i = (x_i, y_i)$$$ ($$$1 \le i \le n$$$) and the Eye point $$$E = (x_n, y_n + H)$$$. Each relief point defines its own angle $$$\alpha_i$$$, which is measured counter-clockwise between positive direction of the OX axis and the $$$(E, p_i)$$$ vector. Now, having two relief points $$$p_i$$$ and $$$p_j$$$ ($$$i < j$$$), it can be said that $$$p_i$$$ is hidden from the Eye if $$$\alpha_i > \alpha_j$$$. When this check is implemented in the solution, to avoid the precision loss, it is recommended to use vector product and analyse its sign to understand the relation of the angles. This check is done in $$$O(1)$$$ time.
Being able to understand when a point is hidden from the Eye by another point, it is possible to calculate, which part of a segment $$$(p_i, p_{i + 1})$$$ is seen by the Eye. First of all let's note, that if the segment left point $$$p_i$$$ is hidden by its right point $$$p_{i + 1}$$$, then the entire segment is hidden from the Eye. Now, we have the situation when left segment point is not hidden from the Eye by its right point. But the segment or its part can still be hidden by the highest mountain (point $$$M$$$), which is a point with minimal angle from all relief points, located to the right of our segment. Here three cases are possible:
• both $$$p_{i}$$$ and $$$p_{i + 1}$$$ are hidden by $$$M$$$ — in this case the entire segment is hidden and we switch to the next segment;
• both $$$p_{i}$$$ and $$$p_{i + 1}$$$ are visible by the Eye (not hidden by the highest mountain $$$M$$$) — in this case the entire segment is visible and we should add its length to the answer;
• left segment point $$$p_i$$$ is visible by the Eye, but right segment point $$$p_{i + 1}$$$ is hidden by $$$M$$$ — in this case we need to find intersection point $$$I$$$ of the segment $$$(p_i, p_{i + 1})$$$ and the ray $$$(E, M)$$$. What is left - add length of $$$(p_i, I)$$$ segment to the answer.
Now, let's conclude the final algorithm:
1. Iterate over all relief segments from right to left, keeping the highest mountain point $$$M$$$.
2. Analyze how left and right points of the current segment are located relatively to each other and point $$$M$$$.
3. Recalculate $$$M$$$, taking points of the current segments as candidates for the highest mountain.