Largest Triangle

문제

A “terrain” is an $xx$-monotone polygon defined by the points $p_1,\dots ,p_{n}p\_1,\; \backslash dots\; ,\; p\_n$ where each point $p_{i}p\_i$ has coordinates $(x_i,y_i)(x\_i\; ,\; y\_i)$, and the following three conditions hold:

• $y_1=y_n=0y\_1\; =\; y\_n\; =\; 0$
• $y_i>0y\_i\; >\; 0$ for
• for

Given a terrain defined by the points $p_1,\dots ,p_{n}p\_1,\; \backslash dots\; ,\; p\_n$, find the largest triangle that fits entirely within the terrain, and one of its three vertices is positioned at one of the terrain points $p_{2}p\_2$ through $p_{n-1}p\_\{n-1\}$.

[이미지 1]

입력

The first line of input contains an integer $nn$, representing the number of points in the terrain ($3\le n\le {10}^{5}3\; \backslash le\; n\; \backslash le\; 10^5$). The $ii$^th line in the following $nn$ lines consists of two space-separated integers $x_{i}x\_i$ and $y_{i}y\_i$, representing the point $p_{i}p\_i$ of the terrain ($0\le x_i,y_i\le {10}^{9}0\; \backslash le\; x\_i\; ,\; y\_i\; \backslash le\; 10^9$).

출력

Print the area of the largest triangle contained within the terrain. Your output will be considered correct if its absolute or relative error is at most ${10}^{-6}10^\{-6\}$.