P13799 [SWERC 2023] Break a leg!

:::align{center}  ::: 霹雳舞首次成为奥运会项目。而你有机会参与其中！不过，你参与的是评审团……更准确地说，你需要搭建评审团前面的桌子：即便如此，这也是一项了不起的成就，祝贺你！ 实际上，桌面的顶板已经搭建完成：它是平面的，宽度和密度均匀，其形状为一个 $N$ 边的非自交多边形 $P_1 P_2 \dots P_N$ 的内部，且没有三点共线（即不存在一条直线经过三个或以上的顶点）。你有三根长度相同且宽度可以忽略不计的桌腿。你的任务是将它们分别放在桌子的三个不同顶点上，使得桌子在这三根桌腿上能够保持稳定。换句话说，你需要选择多边形的三个顶点 $P_i$、$P_j$ 和 $P_k$，使得多边形的重心位于三角形 $P_i P_j P_k$ 的内部（不在其边界上）。 你有多少种不同的放置桌腿的方法？如果两种放置方式仅仅是桌腿的排列不同，则不计为不同的方式。

第一行包含一个整数 $N$。接下来有 $N$ 行，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示顶点 $P_i$ 的 $x$ 坐标和 $y$ 坐标。 **数据范围** - $3 \leq N \leq 100\,000$； - $-1\,000\,000 \leq x_i \leq 1\,000\,000$ 且 $-1\,000\,000 \leq y_i \leq 1\,000\,000$，对所有 $i \leq N$； - 对于任意 $1 \leq i < j < k \leq N$，顶点 $P_i$、$P_j$ 和 $P_k$ 不共线； - 多边形 $P_1 P_2 \dots P_N$ 是非自交的。

输出一行一个整数，表示能够使桌子保持稳定的桌腿放置方法数。

由 ChatGPT 4.1 翻译