题目描述

圣诞集市中有 $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 CONTEST #3 Task 5 Kućice。

本题分值按 COCI 原题设置，满分 $110$。