答えの計算について

同一直線上にない \(3\) 点からなる組をいくつ作れるかという問題です。答えは明らかに \(\lfloor\frac{N}{3}\rfloor\) 以下です。

まず \(N\) 点のうち \(N-\lfloor\frac{N}{3}\rfloor+1\) 点以上の点が直線上にあるような直線 \(L\) が存在するような場合について考えます。この場合、\(L\) 上にない点の数を \(k\) とおくと、 \(2k \leq N-k\) であるため、 \(L\) 上にある点から \(2\) 点、 \(L\) 上にない点から \(1\) 点組み合わせることで \(k\) 個の三角形が作れます。一方、 \(k+1\) 個以上の三角形を作る場合、 \(L\) 上の点を \(3\) 点用いる組が必ず存在し、非退化な三角形という条件に違反してしまうため、 \(k+1\) 個以上の三角形を作ることはできません。よって答えは \(k\) と求まります。

つぎに上記のような直線が存在しない場合を考えますが、実はこの場合答えは \(\lfloor\frac{N}{3}\rfloor\) です。このことを認めると、答えの計算は上記のような直線の存在判定と直線上の点の数の計算ができればよく、直線としては \(N\) 点のうち \(2\) 点以上を通る \(O(N^2)\) 本の直線のみを考えればいいため、各直線上に点があるかの判定を愚直にやっても \(O(N^3)\) 時間で計算でき、十分高速です。

上記の事実の証明

では上記のような直線が存在しない場合答えが \(\lfloor\frac{N}{3}\rfloor\) になることを \(N\) についての帰納法で証明します。 \(N=3,4,5\) に対しては明らかです。

\(N\) 点未満のケースに対して上記が成り立つことを仮定して \(N\) 点でも成り立つことを示します。まず適当に \(3\) 点をとって三角形を作ります（上記のような直線が存在しないことから必ず可能）。これで残った \(N-3\) 点に対し上記のような直線が存在しない場合は帰納法の仮定から示せます。

では残った \(N-3\) 点に対し \(N-3-\lfloor\frac{N-3}{3}\rfloor+1\) 点以上通る直線 \(L\) が存在するケースを考えます。 \(N-3-\lfloor\frac{N-3}{3}\rfloor+3=N-\lfloor\frac{N}{3}\rfloor + 1\) 点通る直線は存在しないという仮定から、 \(N-3-\lfloor\frac{N-3}{3}\rfloor+1, N-3-\lfloor\frac{N-3}{3}\rfloor+2\) 点を通る直線 \(L\) が存在するケースを考えればいいです。

まず \(N-3-\lfloor\frac{N-3}{3}\rfloor+2 = N -\lfloor\frac{N}{3}\rfloor\) 点通る直線 \(L\) が存在する場合ですが、これは \(N\) 点からはじめて \(L\) 上の \(2\) 点と \(L\) 上にない \(1\) 点を組み合わせることで \(\lfloor \frac{N}{3} \rfloor\) 個の三角形を作ることができます。

つぎに \(N-3-\lfloor\frac{N-3}{3}\rfloor+1 = N-1-\lfloor\frac{N}{3}\rfloor\) 点を通る直線 \(L\) が存在する場合を考えます。 \(N\) 点から選んだ \(3\) 点のうち、 \(L\) 上にあったものは \(1\) 個以下です。 \(L\) 上から \(1\) 個取ってた場合は \(L\) は \(N\) 点のうち \(N-\lfloor\frac{N}{3}\rfloor\) 点を通る直線で、これは先ほどのケースと同様に \(\lfloor\frac{N}{3}\rfloor\) 個の三角形が作れます。最初に選ぶ \(3\) 点として \(L\) 上から \(1\) つもとってない場合は \(L\) 上から \(2\) 点とるように修正すると、 \(N\) 点から \(3\) 点とった後 \(L\) 上の点は \(N-3-\lfloor\frac{N}{3}\rfloor\) 点だけ残っているので、 \(L\) は条件を満たす直線ではなくなります。他に条件を満たす直線が存在するケースとして \(L\) 上にない \(\lfloor\frac{N}{3}\rfloor\) 点と \(L\) 上の \(1\) 点を通る直線が考えられますが、これが条件を満たすのは \(N-3-\lfloor\frac{N-3}{3}\rfloor+1 \leq \lfloor\frac{N}{3}\rfloor + 1\) で \(N=6\) のときです。この場合は図を書いてみると、適切に \(3\) 点を選びなおせば三角形を \(2\) つ作れることが示せます。