#arc082c. [arc082_c]ConvexScore

[arc082_c]ConvexScore

给定平面上 NN 个点的坐标 xi,yix_i,y_i。从这 NN 个点中选出一些可以形成凸包的点,构成点集 SS 。点集 SS 形成的凸包是指存在顶点的集合与 SS中的点一致的正面积的凸多边形。但是,凸多边形的内角必须全部不足180°。

例如图中,点集 { A,C,EA,C,E }, { B,D,EB,D,E } 即为可以构成凸包的集合,而 { A,C,D,EA,C,D,E }, { A,B,C,EA,B,C,E }, { A,B,CA,B,C }, { D,ED,E }, \varnothing 都是不能构成凸包的点集。

对于选出来的集合 SS,在 NN 个点中,将 SS 形成的凸包的内部和边上(包括顶点)包含的点的个数设为 nn,将 SS 的贡献定义为2nS2^{n-|S|}

请计算 NN 个点能选出的所有集合 SS 能构成的凸包的贡献和。

但是,由于答案可能会变得非常大,所以请将贡献和对 998244353998244353 取模。