引理:答案为 $2n-2-$ 凸包上的点数。
首先证明这是答案的下界。设最外层凸包点数为 $l_1$,把这些点去掉,对于剩下的点再求一次凸包得到第二层凸包点数 $l_2$……以此类推,我们可以把这些点划分成 $k$ 个相互包含的凸包,点数分别为 $l_1,l_2,\cdots,l_k$。
对于相邻两层凸包之间的部分进行三角剖分,可以得到 $l_i+l_{i+1}$ 个三角形,最里面的凸包直接三角剖分,因此总共有 $(l_1+l_2)+(l_2+l_3)+\cdots+(l_{k-1}+l_k)+(l_k-2)=2n-2-l_1$ 个三角形,这些三角形两两没有交,因此这是答案的下界。
其次,存在一个构造可以达到这个下界。
随机一个向量 $p$,使得任意两个蓝点构成的向量不与 $p$ 平行,令 $|p| \rightarrow 0$,同时在每个点 $+p$ 和 $-p$ 位置放两个点,可以证明这 $2n$ 个点满足要求。
这是因为把一个三角形的三个角平移到一起刚好可以覆盖 $180$ 度,根据抽屉原理必然有一个点落在这里。
但是 $2n$ 个点多了,我们把所有在凸包外面的红点删掉(注意凸包最两侧的点可以删掉 $2$ 个红点),因此剩余的总点数恰好为 $2n-2-$ 凸包点数。
证毕。
上述引理的证明过程也给出了构造。复杂度瓶颈在于 spj,是 $O(n^3 \cdot ans)$ 的。
Bonus:把 spj 的复杂度降为 $O(n^2(n+ans))$。