对于凸包点集 S ,其贡献为 $2^k$ ,其中 k 是该凸包包含的点数除去顶点.
那么答案就是合法的 S 并 U 的点集数量.
合法指的是什么?指的就是存在凸包.
也就是统计共线的点集数,n 很小,枚举两个点,它们唯一确定一条直线,
然后再暴力统计该直线上有多少点即可,这样一个 X 会被算多次,除掉算重次数即可.
另外也可以枚举共线 X 的两个端点,然后暴力统计端点构成的线段之间有多少点,设为 k ,
那么这两个端点对不合法点集的贡献就是 $2^k$ ,这样的好处是不会算重,更好理解.
事实上统计一条直线上的点数有更优秀的做法,可以做到 $O(n^2logn)$ ,