[Q] Make Many Triangles

考察
1. N <= 300と少ない。O(N^2)くらい計算できる
2. 同一直線上にある点集合Xと、そうじゃない点集合Yがわかればうれしい。
3. Xの3点を結んだ3角形は直線になってしまうからいけない。どこか1つでもYの点を組み合わせれば3角形が作れることが分かる。
4. Xの最大数を求めたら、YはN - {Xの個数}で求まる。
5. 答えはmin(N / 3, Y)になる。
XがたくさんあればYの個数だけ三角形が作れるし、
Yがたくさんあれば、自由に三角形を構築でき、最大N/3個まで作れる。

6. どうやって点集合Xの最大数を求めよう？
7. 点i(0~N)を原点とみなした場合の、その他の点の傾きを調べる。同じ傾きの最大数がXの候補になる。

実装

int main()
{
  cincout();

  ll N;
  cin >> N;
  vector<ll> X(N), Y(N);
  rep(i, N) cin >> X[i] >> Y[i];

  ll mx_cnt = 0;
  rep(i, N) // 原点iとする
  {
    ll x0 = 0;
    map<ld, ll> mp;
    rep(j, N)
    {
      if (i == j) continue;
      ll x = X[i] - X[j];
      ll y = Y[i] - Y[j];
      if (x == 0)
      {
        x0++;
      }
      else
      {
        ld k = (ld)y / x;
        mp[k]++;
      }
    }
    for (auto [d, cnt] : mp)
      chmax(mx_cnt, cnt + 1);
    chmax(mx_cnt, x0 + 1);
  }
  // 1. 最大でN / 3個の三角形ができる
  // 2. mx_cntの3点では直線になってしまう。N - mx_cntの集合Yから1つ選ぶ必要がある。
  ll ans = min(N - mx_cnt, N / 3);
  cout << ans << endl;
}

https://atcoder.jp/contests/arc173/submissions/51131539