H - Two Convex Sets Editorial /

Time Limit: 4 sec / Memory Limit: 2048 MiB

配点 : 100 点

Problem Statement

A set of points U in the xy-plane is called good if no point in U lies in the interior of the convex hull of U. Note that the empty set is considered good.

You are given N distinct points v_1, v_2, \dots, v_N in the xy-plane. The coordinates of the point v_i are (x_i, y_i). No three distinct points are collinear.

Count the number of subsets S of V = \lbrace v_1, v_2, \dots, v_N \rbrace such that both S and V \setminus S are good sets.

Constraints

  • All input values are integers.
  • 1 \le N \le 40
  • |x_i|,|y_i|\le 10^6
  • (x_i,y_i)\neq (x_j,y_j)\ (i\neq j)
  • No three distinct points are collinear.

Input

The input is given in the following format:

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

Output

Output the answer.

Sample Input 1

4
0 0
3 0
0 3
1 1

Sample Output 1

14

Except for \emptyset and V, all other sets S satisfy the condition.

Sample Input 2

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

Sample Output 2

256

Sample Input 3

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

Sample Output 3

0

配点 : 100 点

問題文

xy 平面上の点の集合 U が 良い集合 であるとは、 U の凸包の内部に U の点を含まないことを言います。ただし、空集合は良い集合です。

xy 平面上の相異なる N 個の点 v_1,v_2,\dots ,v_N が与えられます。点 v_i の座標は (x_i,y_i) です。これらのうちどの相異なる 3 点も同一直線上に位置することはありません。

V = \lbrace v_1, v_2, \dots, v_N \rbrace の部分集合 S であって、 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)
  • どの相異なる 3 点も同一直線上に位置しない

入力

入力は以下の形式で標準入力から与えられる。

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