#P18241. Two Convex Sets

Two Convex Sets

Two Convex Sets

对于平面上的点集 UU,如果 UU 中没有任何点位于 UU 的凸包内部,则称 UU 是一个 好点集。特别地,空集也是好点集。

给定 NN 个互不相同的点

V={v1,v2,…,vN},vi=(xi,yi).V=\{v_1,v_2,\ldots,v_N\},\qquad v_i=(x_i,y_i).

保证任意三个不同的给定点都不共线。

求有多少个子集 S⊆VS\subseteq V,使得 SS 和 V∖SV\setminus S 都是好点集。

统计的是子集 SS 的数量,互为补集的两个不同子集分别计数。输出准确的整数答案,不取模。

输入格式

第一行一个整数 NN。

接下来 NN 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个点。

输出格式

输出一个整数,表示满足要求的子集数量。

数据范围

  • 所有输入量均为整数。
  • 1≤N≤401\le N\le40。
  • ∣xi∣,∣yi∣≤106|x_i|,|y_i|\le10^6。
  • 给定的点两两不同。
  • 任意三个不同的给定点都不共线。

样例 1

输入

4
0 0
3 0
0 3
1 1

输出

14

说明

除了空集 ∅\varnothing 和全集 VV,其他所有子集 SS 都满足要求。

样例 2

输入

8
1 0
2 0
3 1
3 2
2 3
1 3
0 2
0 1

输出

256

样例 3

输入

10
0 0
1 1
7 1
1 7
3 2
2 3
4 2
2 4
5 4
4 5

输出

0