分数: 700 点
问题陈述
你被给予 N 点 (x_i,y_i) 位于二维平面上。 考虑一个子集 S 的 N 形成凸多边形的点。 这里,我们说一组点 S 形成凸多边形 当存在一个面积为正的凸多边形且其顶点集与 S。多边形的所有内角必须严格小于 180°.
例如,在上图中,{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.