← 返回题目列表

AtCoder · ttpc2024_1_h

H. 两个凸集

中文机器翻译题面 查看原题

配点 : 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