Largest Triangle

A terrain is an $x$-monotone polygon defined by the points $p_1, \dots, p_n$, where each point $p_i$ has coordinates $(x_i, y_i)$, and the following three conditions hold:

• $y_1 = y_n = 0$
• $y_i > 0$ for $1 < i < n$
• $x_i < x_{i+1}$ for $1 \le i < n$

Given a terrain defined by the points $p_1, \dots, p_n$, find the largest triangle that lies entirely within the terrain and has one of its three vertices at one of the terrain points $p_2$ through $p_{n-1}$.

The first line contains an integer $n$, the number of points in the terrain ($3 \le n \le 10^5$). Each of the next $n$ lines contains two space-separated integers $x_i$ and $y_i$, the coordinates of point $p_i$ ($0 \le x_i, y_i \le 10^9$).

Print the area of the largest triangle that lies entirely within the terrain. A answer is accepted if its absolute or relative error is at most $10^{-6}$.