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 翻译