#P18241. Two Convex Sets
Two Convex Sets
Two Convex Sets
对于平面上的点集 ,如果 中没有任何点位于 的凸包内部,则称 是一个 好点集。特别地,空集也是好点集。
给定 个互不相同的点
保证任意三个不同的给定点都不共线。
求有多少个子集 ,使得 和 都是好点集。
统计的是子集 的数量,互为补集的两个不同子集分别计数。输出准确的整数答案,不取模。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示第 个点。
输出格式
输出一个整数,表示满足要求的子集数量。
数据范围
- 所有输入量均为整数。
- 。
- 。
- 给定的点两两不同。
- 任意三个不同的给定点都不共线。
样例 1
输入
4
0 0
3 0
0 3
1 1
输出
14
说明
除了空集 和全集 ,其他所有子集 都满足要求。
样例 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