配点 : $700$ 点

問題文

二次元平面上に配置された $N$ 個の点 $(x_i,y_i)$ が与えられます。 $N$ 点の部分集合 $S$ であって、凸多角形をなすものを考えます。 ここで点集合$S$が凸多角形をなすとは、 頂点の集合が $S$ と一致するような正の面積の凸多角形が存在することとします。ただし、凸多角形の内角は全て $180^\circ$ 未満である必要があります。

例えば下図では、$S$ として {$A,C,E$}, {$B,D,E$} などは認められますが、{$A,C,D,E$}, {$A,B,C,E$}, {$A,B,C$}, {$D,E$}, {} などは認められません。

$S$ に対し、$N$ 個の点のうち $S$ の凸包の内部と境界 (頂点も含む) に含まれる点の個数を $n$ とおき、 $S$ のスコアを、$2^{n-|S|}$ と定義します。

凸多角形をなすような考えうる全ての $S$ に対してスコアを計算し、これらを足し合わせたものを求めてください。

ただし答えはとても大きくなりうるので、$998244353$ で割った余りをかわりに求めてください。

制約

• $1 \leq N \leq 200$
• $0 \leq x_i,y_i<10^4 (1 \leq i \leq N)$
• $i \neq j$ なら $x_i \neq x_j$ または $y_i \neq y_j$
• $x_i,y_i$ は整数

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_N$ $y_N$

出力

スコアの総和を $998244353$ で割った余りを出力せよ。

4
0 0
0 1
1 0
1 1

5

$S$ として三角形（をなす点集合）が $4$ つと四角形が $1$ つとれます。どれもスコアは $2^0=1$ となるので、答えは $5$ です。

5
0 0
0 1
0 2
0 3
1 1

11

スコア $1$ の三角形が $3$ つ、スコア $2$ の三角形が$2$つ、スコア $4$ の三角形が $1$ つあるので、答えは $11$ です。

1
3141 2718

0

$S$ として考えられるものがないので、答えは $0$ です。