ARC082C ConvexScore

题意：给出平面上的点集 。（保证不存在重点）

对于 ，若 中的点可以构成严格凸多边形，记被 包在内部（包括边界）的点集为 ，则贡献为 。

求所有 的贡献和，答案对 取模。

，时限 。

---

这个 看起来很刻意，考虑组合意义。

记 ， 即为 的子集个数。

问题可以转化为，统计满足 的二元组 的个数。

可以发现，二元组 和点集 是一一对应的，因为根据点集 求严格凸包即可得到唯一的 。

于是，问题转化为：求有严格凸包的点集个数。

显然若点集不共线的符合条件，故问题又等价于：求共线点集个数。

单个点必定是“共线”的，单独计算。若有两个点，那么直线是唯一的。

枚举两个点确定直线，然后数有多少个点在直线上，记为 ，则贡献为 。

暴力枚举，复杂度为 ，可以通过。