eolymp
bolt
Try our new interface for solving problems
Problems

Au reservoir

Au reservoir

Consider a polygonal chain. Its coordinates (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), (\textbf{x_3}, \textbf{y_3}), …, (\textbf{x_N}, \textbf{y_N}) satisfy inequalities \textbf{x_1} < \textbf{x_2} < \textbf{x_3} < … < \textbf{x_N} and \textbf{y_i} ≠ \textbf{y_\{i+1\}} for all \textbf{i}. Let’s draw rays upward from the leftmost (\textbf{x_1}, \textbf{y_1}) and the rightmost (\textbf{x_N}, \textbf{y_N}) vertices. Then let’s transform the plane figure into three-dimensional body with constant thickness of \textbf{1}. \includegraphics{https://static.e-olymp.com/content/df/df62483182e53a9d5a61d2f158cc6038dcce0582.jpg} A reservoir was made according to these rules. Its front and back sides are plain, vertical, parallel each to other, and are at distance \textbf{1} each from other. The left and right sides (obtained from the verticals rays) are also plain, vertical and parallel each to other. The bottom of the reservoir is obtained from the initial polygonal chain. The reservoir is mounted so that irrespective of the bottom shape and of filling level it will never turn over. \textbf{V} cubic units of water are carefully filled into the reservoir, from its left side. Your task is to write a program, calculating the area of resulting water surface. \InputFile Program should read from input the number of vertices in polygon chain \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{123456}), than \textbf{N} pairs of integers \textbf{x_1} \textbf{y_1} \textbf{x_2} \textbf{y_2} … \textbf{x_N} \textbf{y_N}, meaning the coordinates of the vertices, and, at last, the water volume \textbf{V}. All coordinates are integers in range from \textbf{--10^6} to \textbf{10^6}; volume is an integer in range \textbf{0} ≤ \textbf{V} ≤ \textbf{10^12}. \OutputFile Program should output exactly one floating-point number --- the area of final water surface. Absolute accuracy of the answer should not be worse than \textbf{10^\{--3\}}. \includegraphics{https://static.e-olymp.com/content/7b/7b3b6726f6219b430c75c28a2923542e093a6149.jpg}
Time limit 1 second
Memory limit 64 MiB
Input example #1
5
-1 2 1 0 3 3 5 0 7 1 
8
Output example #1
6.309401
Source International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011