AT_relay2018_g バス停と凸包

在二维平面上有 $N$ 个公交车站，第 $i$ 个公交车站的坐标为 $(x_i, y_i)$，其中 $x_i, y_i$ 都是整数。 すぬけ君想要从这 $N$ 个公交车站中选择至少 $3$ 个，计算这些点的凸包（包含所选点集合的所有点的最小面积凸多边形）的面积，并对所有选择方式的面积求和。你需要帮他计算这个值。 设所有面积的总和为 $a/2$，可以证明 $a$ 一定是整数。请输出 $a$ 除以 $10^9+7$ 的余数。

输入通过标准输入给出，格式如下： > $N$ > $x_1$ $y_1$ > $x_2$ $y_2$ > $\vdots$ > $x_N$ $y_N$

请输出面积总和的 $2$ 倍对 $10^9+7$ 取模的结果。

## 限制条件 - $3 \leq N \leq 2000$ - $|x_i|, |y_i| \leq 10000$ - $(x_i, y_i) \neq (x_j, y_j)$（$1 \leq i < j \leq N$） - 给定的任意 $3$ 个点都不共线 - 输入的所有值都是整数 ## 样例解释 1 - 选择第 $1$、$2$、$3$ 个点时，凸包面积为 $1/2$。 - 选择第 $1$、$2$、$4$ 个点时，凸包面积为 $1/2$。 - 选择第 $1$、$3$、$4$ 个点时，凸包面积为 $1$。 - 选择第 $2$、$3$、$4$ 个点时，凸包面积为 $2$。 - 选择第 $1$、$2$、$3$、$4$ 个点时，凸包面积为 $2$。 因此，面积总和为 $1/2+1/2+1+2+2=6$。面积总和的 $2$ 倍对 $10^9+7$ 取模的结果是 $12$。 由 ChatGPT 4.1 翻译