#arc082c. [arc082_c]ConvexScore
[arc082_c]ConvexScore
给定平面上 个点的坐标 。从这 个点中选出一些可以形成凸包的点,构成点集 。点集 形成的凸包是指存在顶点的集合与 中的点一致的正面积的凸多边形。但是,凸多边形的内角必须全部不足180°。
例如图中,点集 { }, { } 即为可以构成凸包的集合,而 { }, { }, { }, { }, 都是不能构成凸包的点集。
对于选出来的集合 ,在 个点中,将 形成的凸包的内部和边上(包括顶点)包含的点的个数设为 ,将 的贡献定义为。
请计算 个点能选出的所有集合 能构成的凸包的贡献和。
但是,由于答案可能会变得非常大,所以请将贡献和对 取模。