/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
平面上に N 個の点 P_1, P_2, \dots, P_N があり、P_i の座標は (X_i, Y_i) です。どの 3 点も同一直線上にないことが分かっています。
要素数が 3 以上であるような \{ P_1, P_2, \dots, P_N \} の部分集合 S に対し、S の凸包を次のように定義します。
- S に含まれる全ての点を周上または内部に含むような凸多角形のうち、面積が最小のもの。
凸包の面積が整数となるような S の総数を (10^9 + 7) で割ったあまりを求めてください。
制約
- 3 \leq N \leq 80
- 0 \leq |X_i|, |Y_i| \leq 10^4
- どの 3 点も同一直線上にない。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを出力せよ。(10^9 + 7) で割ったあまりを求めることに注意すること。
入力例 1
4 0 0 1 2 0 1 1 0
出力例 1
2
\{ P_1, P_2, P_4 \}, \{ P_2, P_3, P_4 \} が条件を満たします。
入力例 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
出力例 2
4060436
Score : 600 points
Problem Statement
We have N points P_1, P_2, \dots, P_N on a plane. The coordinates of P_i is (X_i, Y_i). We know that no three points lie on the same line.
For a subset S of \{ P_1, P_2, \dots, P_N \} with at least three elements, let us define the convex hull of S as follows:
- The convex hull is the convex polygon with the minimum area such that every point of S is within or on the circumference of that polygon.
Find the number, modulo (10^9 + 7), of subsets S such that the area of the convex hull is an integer.
Constraints
- 3 \leq N \leq 80
- 0 \leq |X_i|, |Y_i| \leq 10^4
- No three points lie on the same line.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer. Note that you are asked to find the count modulo (10^9 + 7).
Sample Input 1
4 0 0 1 2 0 1 1 0
Sample Output 1
2
\{ P_1, P_2, P_4 \} and \{ P_2, P_3, P_4 \} satisfy the condition.
Sample Input 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
Sample Output 2
4060436