{"problem":{"name":"F. Flood Season","description":{"content":"_Poor them!_ Whenever rain season comes, the water rises as hell and the most affected region is Northwest Vietnam. Villages, houses, plants, animals, and people are all victims of cruel Nature. S_e","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10227F"},"statements":[{"statement_type":"Markdown","content":"_Poor them!_\n\nWhenever rain season comes, the water rises as hell and the most affected region is Northwest Vietnam. Villages, houses, plants, animals, and people are all victims of cruel Nature.\n\nS_e_o is a civil manager of Northwest Vietnam. As a man with a kind heart, he worries for Northwestern citizens and is willing to do everything to stop the disaster. With only a computer, he roughly models the area of Northwest Vietnam on Cartesian plane. The model is a polyline with n points, each with integer coordinates. He wants to calculate the maximum area that could be filled with water, but his computer breaks down right after he has finished the model. He still keeps the input data and calls for your help!\n\nPlease help him !!\n\nThe first line contains an integer $\" \"n \" \"(2 <= n <= 10^5)$ , the number of points in the polyline\n\nLine 2..$\" \"n + 1$ : Line $i$ contains two numbers $x_i, \" \"y_i (0 <= x_i, \" \"y_i <= 10^6)$ which are x-coordinates and y-coordinates of a point. \n\nIt is guaranteed that $x_i < x_{i + 1}$\n\nOutput: A single line contains a single real number which is the answer. Your output is correct if the difference between your output and the test answer is no larger than $10^(-6)$\n\nThe following image explains the first sample test case\n\n## Input\n\nThe first line contains an integer $\" \"n \" \"(2 <= n <= 10^5)$ , the number of points in the polylineLine 2..$\" \"n + 1$ : Line $i$ contains two numbers $x_i, \" \"y_i (0 <= x_i, \" \"y_i <= 10^6)$ which are x-coordinates and y-coordinates of a point. It is guaranteed that $x_i < x_{i + 1}$\n\n## Output\n\nOutput: A single line contains a single real number which is the answer. Your output is correct if the difference between your output and the test answer is no larger than $10^(-6)$\n\n[samples]\n\n## Note\n\nThe following image explains the first sample test case","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of points in the polyline.  \nLet $ P = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the sequence of points with integer coordinates, where $ x_i < x_{i+1} $ for all $ i $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq x_i, y_i \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ x_i < x_{i+1} $ for all $ i \\in \\{1, \\dots, n-1\\} $\n\n**Objective**  \nCompute the maximum area bounded above by the polyline and below by the \"water level\" formed by connecting each point to the minimum height between its left and right neighbors, i.e., the area under the polyline but above the \"filling\" level defined by:  \nFor each segment $ [x_i, x_{i+1}] $, the water surface is at height $ \\min(y_i, y_{i+1}) $, and the area is the integral of $ \\max(0, y_i - \\min(y_i, y_{i+1}), y_{i+1} - \\min(y_i, y_{i+1})) $ — but more precisely, the area between the polyline and the *lower envelope* formed by local minima.\n\nActually, the correct interpretation:  \nThe water fills to the level of the *lower of the two endpoints* of each segment, and the area is the sum over all segments of the trapezoid above that level but below the polyline.\n\nBut standard interpretation in such problems:  \nThe area of water that can be held is the area *under* the polyline and *above* the \"filling curve\" which is the *lower envelope* formed by connecting each point to the minimum of its adjacent heights — but this is equivalent to computing the area between the polyline and the \"water surface\" that is the *minimum of the prefix maximum and suffix maximum* at each point.\n\nActually, standard solution:  \nFor each point $ i $, define:  \n- $ L_i = \\max\\{y_1, y_2, \\dots, y_i\\} $ (prefix maximum)  \n- $ R_i = \\max\\{y_i, y_{i+1}, \\dots, y_n\\} $ (suffix maximum)  \n\nThen the water level at point $ i $ is $ h_i = \\min(L_i, R_i) $, and the water area is the area between the polyline $ y_i $ and the water level $ h_i $, integrated over $ x $.\n\nBut since it's a polyline, we compute the area between the water surface (piecewise linear between $ h_i $) and the ground (polyline), which is:\n\n$$\n\\text{Area} = \\sum_{i=1}^{n-1} \\frac{(x_{i+1} - x_i)}{2} \\cdot \\left[ (h_i - y_i) + (h_{i+1} - y_{i+1}) \\right]\n$$\n\nBut only if $ h_i \\ge y_i $ and $ h_{i+1} \\ge y_{i+1} $, which they are by construction.\n\nActually, the water surface is the \"skyline\" defined by $ h_i = \\min(\\text{prefix\\_max}_i, \\text{suffix\\_max}_i) $, and the area is:\n\n$$\n\\sum_{i=1}^{n-1} \\left( \\frac{(x_{i+1} - x_i)}{2} \\cdot \\left( (h_i - y_i) + (h_{i+1} - y_{i+1}) \\right) \\right)\n$$\n\nBut note: if $ h_i = y_i $, then no water above that point.\n\nSo formally:\n\n**Objective**  \nDefine:  \n- $ L_i = \\max_{1 \\le j \\le i} y_j $  \n- $ R_i = \\max_{i \\le j \\le n} y_j $  \n- $ h_i = \\min(L_i, R_i) $ for each $ i \\in \\{1, \\dots, n\\} $\n\nCompute the total water area:  \n$$\n\\text{Area} = \\sum_{i=1}^{n-1} \\frac{x_{i+1} - x_i}{2} \\cdot \\left( (h_i - y_i) + (h_{i+1} - y_{i+1}) \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10227F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}