配点 : 100 点
问题陈述
一组点 U 在 xy-plane 被称为 好 如果没有意义 U 在于 内饰 的凸包 U。请注意,空集被认为是好的。
你被给予 N 不同点 v_1, v_2, \dots, v_N 在 xy- 平面。点的坐标 v_i 是 (x_i, y_i)。没有三个不同的点共线。
计算子集的数量 S of V = \lbrace v_1, v_2, \dots, v_N \rbrace 这样两者 S 和 V \setminus S 是很好的套装。
约束
- 所有输入值均为整数。
- 1 \le N \le 40
- |x_i|,|y_i|\le 10^6
- (x_i,y_i)\neq (x_j,y_j)\ (i\neq j)
- 没有三个不同的点共线。
输入
输入按以下格式给出:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
输出
输出答案。
示例输入 1
4 0 0 3 0 0 3 1 1
示例输出 1
14
除了 \emptyset 和 V,所有其他集合 由 S 满足条件。
示例输入 2
8 1 0 2 0 3 1 3 2 2 3 1 3 0 2 0 1
示例输出 2
256
示例输入 3
10 0 0 1 1 7 1 1 7 3 2 2 3 4 2 2 4 5 4 4 5
示例输出 3
0