公式解説を前提とします．決定的に \(O(N)\) 時間で解く方法を解説します．

\(N\) 個の点全体を次のような集合に分割します：

• 同じ頂点を使わない三角形 \(T_1, \ldots, T_n\)
• \(T_1, \ldots, T_n\) に使われずに余っている点全体の集合 \(S\)．ただし \(S\) 内の点は同一直線上にあるようにする．

点をひとつずつ追加しながら，次のような手順をとることで目標を達成できます：

• 点 \(p\) を追加するとき，\(|S|\leq 1\) ならば \(S\) に \(p\) を追加する．
• \(S\geq 2\) のとき，\(S\) のうち好きに選んだ \(2\) 点と \(p\) で三角形を作れるかどうかを調べる．三角形を作れるならば三角形 \(T_{n+1}\) を作成し，\(S\) からいま選んだ 2 点を削除する．作れないならば \(S\) に \(p\) を追加する．

\(N\) 個の点全体を分割し終えた時点で \(|S|\leq 2\) ならば，\(\lfloor N/3\rfloor\) 個の三角形が構成できているので，これが本問の答えとなります．

\(N\) 個の点全体を分割し終えた時点で \(|S|\geq 3\) であるとします．

直線 \(L\) が公式解説で出てきた「 \(N-\lfloor N/3\rfloor\) 点以上の点が直線上にあるような直線 \(L\)」であるとします．この \(L\) は，特に全体の \(2/3\) 以上の割合の点を含みます．\(L\) は各 \(T_i\) の頂点を \(2\) つまでしか含まないので，\(L\) は \(S\) の点も \(2/3\) 以上の割合で含む必要があります．特に \(S\) の点を \(2\) 点以上含みます．

\(S\) のすべての点は同一直線上にあるのでしたから，このような直線 \(L\) として可能なものはひとつしかありません．

したがってこの場合，答は次のようになります：

\(S\) のうち適当な \(2\) 点を通る直線を \(L\) とする．入力で与えられる点のうち \(L\) 上にある点の個数 \(k\) を求める． \(k\geq N-\lfloor N/3\rfloor\) ならば答は \(N-k\) である．そうでなければ答は \(\lfloor N/3\rfloor\) である．

• 解答例：https://atcoder.jp/contests/arc173/submissions/51129921

本アルゴリズムと類似のアルゴリズムとして，多重集合から過半数を持つ要素があるかを調べる Boyer–Moore majority vote algorithm があります．本解説と合わせて確認してみてください．