P14707 [ICPC 2023 Tehran R] Largest Triangle

一个“地形”是一个 $x$-单调多边形，由点 $p_1, \ldots, p_n$ 定义，其中每个点 $p_i$ 的坐标为 $(x_i, y_i)$，并且满足以下三个条件： - $y_1 = y_n = 0$ - 对于 $1 < i < n$，有 $y_i > 0$ - 对于 $1 \leq i < n$，有 $x_i < x_{i+1}$ 给定由点 $p_1, \ldots, p_n$ 定义的地形，找出能够完全放置在地形内的最大三角形，且其三个顶点之一位于地形点 $p_2$ 到 $p_{n-1}$ 中的某一个上。 :::align{center}  :::

输入的第一行包含一个整数 $n$，表示地形中的点数 ($3 \leq n \leq 10^5$)。接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示地形中的点 $p_i$ ($0 \leq x_i, y_i \leq 10^9$)。

输出地形内所能容纳的最大三角形的面积。只要你的输出的绝对或相对误差不超过 $10^{-6}$，即被视为正确。

翻译由 DeepSeek V3 完成