哎哎哎这就是我们洛谷题解的质量

· · 题解

你谷题解区没有任何一篇非随机化题解提到了正确性证明，我觉得这玩意显然不了一点吧。。。

首先你拉一条直线 l，设这条直线穿过了 c 个题目给的整点，那么因为每个三角形都至少要有一个点不在 l 上，就可以得到一个上界是 n-c，而且这个上界在某些条件下也是可以得到的：选 l 上的两个点和 l 外的一个点配对，如果可以把 l 外的点用完就可以得到 n-c 个三角形，有限制 2(n-c)\le c，即 c\ge \frac{2}{3}n。

找到穿过点最多的直线，然后看一下它经过的点数量 c 和 \frac{2}{3}n 的大小关系，如果 c\ge\frac{2}{3}n 则答案为 n-c，否则以上的构造过程无法成立。

然后大胆猜一下，如果 c<\frac{2}{3}n，那么一定能得到上界 \lfloor\frac{n}{3}\rfloor。

考虑证明，先做一个放缩，让 c<\frac{2}{3}n 变成 c\le\lceil\frac{2}{3}n\rceil，这种形式会更好处理。

使用数学归纳法，n=3,4,5 的情况是显然的，对于某个 n\ge 6，因为 c\le\lceil\frac{2}{3}n\rceil，我们总是可以找到一个非退化的三角形。把它删掉，如果剩下的 n-3 个点中还是不存在经过超过 \lceil\frac{2}{3}(n-3)\rceil 个点的直线，归纳即证；否则，设这条直线为 l。

设 l 经过了 c 个点，那么应当有 \lceil\frac{2}{3}(n-3)\rceil<c\le\lceil\frac{2}{3}n\rceil，所以 c 只能是 \lceil\frac{2}{3}n\rceil-1 或 \lceil\frac{2}{3}n\rceil。

若 c=\lceil\frac{2}{3}n\rceil，就有 n-c=\lfloor\frac{n}{3}\rfloor，我们可以通过选 l 上的 2 个点与不在 l 上的一个点的构造方式得到 \lfloor\frac{n}{3}\rfloor 个三角形。

若 c=\lceil\frac{2}{3}n\rceil-1，我们就用两个在 l 上的点和一个不在 l 上的点组一个三角形，那么 l 上就只剩下 \lceil\frac{2}{3}n\rceil-3 个点，l 外只剩下 \lfloor\frac{n}{3}\rfloor 个点，如果有一条直线穿过了 l 外的所有点和 l 中的一个点，要使归纳假设不成立，就要有 \lfloor\frac{n}{3}\rfloor+1>\lceil\frac{2}{3}n\rceil-2，在 n\ge 6 的范围里只有 n=6 满足这个式子，手玩一下不难发现此时仍然可以构造出 \lfloor\frac{n}{3}\rfloor 个三角形。

于是我们就完成了证明。找直线 \Theta(n^3) 暴力找就行。

#include <iostream>

using namespace std;
using LL = long long;

const int kN = 301;

int n, ans;
LL x[kN], y[kN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> x[i] >> y[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      int c = 0;
      for (int k = 1; k <= n; ++k) {
        c += (y[j] - y[i]) * (x[k] - x[i]) == (y[k] - y[i]) * (x[j] - x[i]);
      }
      ans = max(ans, c);
    }
  }
  cout << min(n / 3, n - ans);
  return 0;
}