原本没多太在意，但是今天竟然看这种题的变体看半天没看出来 (只能说写 “人类智慧题” 写多了)
Q.给定一些二维平面的点 ($N \leq 500$)，求在 不重复使用任何一个点的情况下，构成的三角形的个数 ARC-B
显然，如果做过类似的，直接分类讨论，先枚举所有直线，得到这些直线上存在点的个数最大值 $A$
- $A \geq 2 \times (N - A)$, 必然剩余 $A - 2 \times (N - A)$ 个点凑不出三角形。
- $A < 2 \times (N - A)$，存在一种方案能几乎全部凑出三角形，剩余 $N \; \mathrm{mod}\; 3$。
Proof.
第一种情况比较显然，下面考虑第二种情况：
必然最后剩下的点都在一条直线上，因此假设当前所有直线上的点的个数为：
$$x_1\leq x_2 \leq \cdots \leq x_M\quad 3 \times x_M < 2 \times N$$
每次取最大值 $x_M$ 对应的线上的 $2$ 个点和其它线上的 $1$ 个点匹配，此时可能导致 $M$ 条线中的多条线点数减小，我们只关注上述操作后，剩下的线里的点数最大值 $x_M’$
必然有 $x_{M’} \leq x_M$,得到新的序列：
$$x_{1’}\leq x_{2’} \leq \cdots \leq x_{M’}$$
如果：
- $x_{M’} = x_M$，那么 $3 \times x_{M’}$ 与 $2 N’(N’ = N - 3)$，关系有以下两种情况：
- $3 \times x_{M’} < 2 N’$，此时继续往下做类似上面的操作
- $3 \times x_{M’} \geq 2 N’$，使用结论，因此只会剩下：$3 x_{M’} -2 N’ = 3x_M - 2N + 6 =(1)$
- 注意到此时至少 $N > 2 x_M, (1) < 6 - 0.5N$，分类讨论可以证明 $(1) < 3$ ，因此此时答案为 $(1) \;\mathrm{mod}\; 3$，等价于 $N\; \mathrm{mod} \;3$
- $x_{M’} = x_M - 1$ 也有类似的讨论，比上面讨论会简单
- $x_{M’} \leq x_M - 2$，此时有 $3x_{M’} < 2N’$，因此可以继续往下递推，直到答案成为 $N \;\mathrm{mod}\; 3$
#
Practice
