33182번 - 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 fits entirely within the terrain, and one of its three vertices is positioned at one of the terrain points $p_2$ through $p_{n-1}$.

입력

The first line of input contains an integer $n,ドル representing the number of points in the terrain (3ドル \le n \le 10^5$). The $i$^th line in the following $n$ lines consists of two space-separated integers $x_i$ and $y_i,ドル representing the point $p_i$ of the terrain (0ドル \le x_i , y_i \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}$.

제한

힌트