[COCI2021-2022#3] Kućice

圣诞集市中有 $n$ 个摊位。每个摊位可以抽象为平面直角坐标系中的一个点，其坐标为 $x_i,y_i$。 现在每个摊位均有 $50\%$ 的概率违规。所有违规的摊位会被一个栅栏圈住，其中栅栏的形状为所有违规摊位对应的点组成的凸包的边界。当然，一些没有违规的无辜摊位也有可能被圈住。当违规摊位数量小于 $3$ 时，凸包显然会退化为线段、点或空集。 求被圈住摊位的期望数量。可以证明答案可以被表示成 $\frac{m}{2^n}$，其中 $m$ 为正整数。因此只需要输出 $m$ 对 $10^9+7$ 取模后的值即可。

第一行，一个正整数 $n$，表示摊位的数量。 接下来的 $n$ 行，每行两个整数 $x_i,y_i$，表示摊位的坐标。数据保证不存在坐标相同的摊位且任意三个摊位都不共线。

输出 $m$ 对 $10^9+7$ 取模后的值。

1
5 5

1

3
-1 -1
1 -1
0 1

12

5
0 0
-1 0
2 -1
3 2
0 3

83

**【样例 1 解释】** 唯一的摊位违规的概率为 $50\%$，故期望值为 $\frac{1}{2}$。 **【样例 2 解释】** 违规的情况共有 $8$ 种，而每种情况下被圈住的摊位数分别为 $0,1,1,1,2,2,2,3$。故期望值为 $\frac{1}{8}(0+1+1+1+2+2+2+3)=\frac{12}{8}$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（10 pts）：每个点都在由所有点组成的凸包的边界上，同时 $n \ge 3$。 - Subtask 2（30 pts）：除了第一个点外，每个点都在由所有点组成的凸包的边界上，同时 $n \ge 4$，$x_1=y_1=0$。 - Subtask 3（10 pts）：$1 \le n \le 15$。 - Subtask 4（30 pts）：$1 \le n \le 100$。 - Subtask 5（30 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n \le 1000$，$|x_i|,|y_i| \le 10^6$。 **【提示与说明】** **题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 5 Kućice_。** **本题分值按 COCI 原题设置，满分 $110$。**