← 返回题目列表

AtCoder · arc082_c

E. 凸分数

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

分数: 700 点

问题陈述

你被给予 N 点 (x_i,y_i) 位于二维平面上。 考虑一个子集 S 的 N 形成凸多边形的点。 这里,我们说一组点 S 形成凸多边形 当存在一个面积为正的凸多边形且其顶点集与 S。多边形的所有内角必须严格小于 180°.

cddb0c267926c2add885ca153c47ad8a.png

例如,在上图中,{A,C,E} 和 {B,D,E} 形成凸多边形; {A,C,D,E}, {A,B,C,E}, {A,B,C}, {D,E} 和 {} 则不然。

对于给定的集合 S,让 n 是其中的点数 N 凸包内的点 S (包括边界和顶点)。然后,我们将定义 分数 游戏的 of S as 2^{n-|S|}.

计算所有可能集合的分数 S 形成凸多边形,并找到所有这些分数的总和。

但是,由于总和可能非常大,因此打印总和模 998244353.

约束

  • 1≤N≤200
  • 0≤x_i,y_i<10^4 (1≤i≤N)
  • If i≠j, x_i≠x_j or y_i≠y_j.
  • x_i 和 y_i 是整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_N y_N

输出

打印所有分数模数的总和 998244353.


示例输入 1

4
0 0
0 1
1 0
1 1

示例输出 1

5

我们有五种可能的集合: S,四组形成三角形,一组形成正方形。他们每个人的分数都是 2^0=1,所以答案是 5.


示例输入 2

5
0 0
0 1
0 2
0 3
1 1

示例输出 2

11

我们有三个“三角形”,得分为 1 每个,两个“三角形”,得分为 2 每个,以及一个得分为 4。因此,答案是 11.


示例输入 3

1
3141 2718

示例输出 3

0

无法设置为 S,所以答案是 0.