CF1146G - Satanic Panic

题目大意

给定平面上 \(n\) 个点，求能够构成五角星的五元组数目

分析

实际上就是求五元凸包数目，下面直接考虑 \(k\) 元的形式

考虑凸包的两种判定方法：

1.所有转角 \(<\pi\)

然而这并不好实现

2.一个凸包可以根据 \(x_i\) 最大、最小的两个点分成上下两部分，上下分别判断转角 \(<\pi\)

（可以通过随机旋转规避 \(x_i\) 相同的情况）

（这题 \(k\) 较小，或许可以上下暴力枚举？）

一般的情况，枚举 \(x_i\) 最小的点 \(A\)

然后令 \(dp_{i,j}\) 表示当前凸包最后一条折线为 \((i,j)\) ，然后不断接新点

最后合并上下两个凸包

直接实现，单次 \(dp\) 状态 \(O(n^2k)\) ，转移 \(O(n)\) ，复杂度为 \(O(n^4k)\)

优化：

设 \((i,j)\rightarrow (j,k)\) ，可以先确定 \(j\)

然后按照转角顺序枚举 \(k\) ，双指针完成所有 \(k\) 的转移

如果预处理每个点出发的转角序，则预处理 \(O(n^2\log n)\) ，总复杂度为 \(O(n^3k)\)

(Code消失了)