全ての直線が同一直線上に乗っている時、 \(N\) 点全て選べば良いです。以下、そうでないものとします。

印を付けた部分集合について、最も乗っている点の数が多い直線 \(l\) を考えて、以下のように場合分けをします。

パターン A: \(l\) に \(M(\geq 4)\) 点が乗っている状況。この時

• \(M+1\) 点を取る方法は、\(M\) 点に加えて \(l\) に乗っていない点を選べば良いので存在します。
• \(M+2\) 点を取る方法は、 \(l\) を挟んだ両側から \(1\) 点ずつ取る方法であって、その \(2\) 点を結ぶ直線を挟んだ片方には \(l\) 上の \(M\) 点が一切入らないような取り方が考えられます。なお、 \(l\) を挟んだ片方から \(2\) 点 \(X,Y\) を取ると、 \(l\) に \(4\) 点以上乗っていることから、直線 \(XY\) を挟んで片方に \(M\) 点のうちの \(2\) 点が来てしまい、これと \(X,Y\) を選ぶと凸四角形になってしまいます。
• \(M+3\) 点を取ると、\(l\) 上以外の \(3\) 点のうち、どうしても \(l\) の片側に \(2\) 点入ってしまうので、不可能であることが分かります。

パターン B: \(l\) に \(3\) 点乗っている状況。この時

• \(4\) 点を取る方法は、\(l\) 上の \(3\) 点と \(l\) に乗っていない点を選べば良いので存在します。
• \(5\) 点を取る方法は、\(l\) 上の点が \(A,B,C\) と並んでいるとすると、次のような取り方があります。
  • \(l\) を挟んだ両側から \(1\) 点ずつ \(D,E\) 取る方法であって、 \(A,B,C\) がいずれも直線 \(DE\) に対して同じ側または \(DE\) 上に来るような取り方（同じ側でなければ \(A,C,D,E\) が凸四角形を成してしまう。図 1 参照）。
  • \(l\) を挟んだ片方から \(2\) 点 \(D,E\) を取る方法であって、 \(B\) が直線 \(DE\) 上かつ \(A,C\) が直線 \(DE\) を挟んで反対側になるような取り方（直線 \(l\) と \(DE\) の交点が \(B\) よりも \(C\) 側にあれば、 \(A,B,D,E\) が凸四角形を成し、 \(B\) よりも \(A\) 側にあれば \(B,C,D,E\) が凸四角形を成すので、 \(DE\) はちょうど \(B\) を通らなくてはならない。図 2 参照）。
• \(6\) 点を取る方法は、 \(5\) 点を取る方法にさらに \(1\) 点を追加すると考えます。
  • \(l\) を挟んだ片側に \(3\) 点 \(D,E,F\) を取るとすると、 \(5\) 点の時の考察より、直線 \(DE\) および直線 \(DF\) が \(B\) を通る必要があり、 \(B,D,E,F\) の \(4\) 点が同一直線上に並ぶ。これは最も乗っている点の数が多い直線が \(l\) であることに矛盾。
  • \(l\) を挟んだ片側に \(D,E\) があり、反対側に \(F\) があるとする。この時、直線 \(DE\) 上に \(B\) がある必要がある。 \(B,D,E\) がこの順に並ぶとすると、 \(l\) の代わりに直線 \(BE\) について同様のことを考えることで、 \(F,A,D\) か \(F,C,D\) がこの順に一直線上に並んでいる必要があることが分かる。この時、 \(6\) 点は図 3 のように「風車状」に並んでいる。
• \(7\) 点を取る方法は、図 4 より \(7\) 点目を取れる場所がないので、存在しません。

パターン C: \(l\) に \(2\) 点乗っている状況（つまりどの \(3\) 点も同一直線上に乗らない）。この時

• \(3\) 点を取った時、自明に条件は満たされます。
• \(4\) 点を取る方法は、三角形の \(3\) 頂点と、その内部の \(1\) 点という配置になります。
• \(5\) 点を取る方法は存在しません。この事実は Happy ending problem として知られていますが、\(4\) 点を取ってからもう \(1\) 点をどこに取るかと考えるとあまり難しくないでしょう。

以上より、次のように解けます。

• パターン A での最大を求める。\(O(N^2\log N)\) や \(O(N^3)\) 時間。

  求め方の詳細

  直線 \(l\) として考えられるものは高々 \(\binom{N}{2}\) 通りなので、これを固定します。ここに \(2\) 点を追加できる条件は、 \(l\) 上の点のうち端にある点からの偏角を計算すれば判定できます。よって、事前に各点を中心とした偏角ソートを行っておくと、\(l\) と \(2\) 点からなるものが存在するかどうかが全体で \(O(N^2\log N)\) で求まります（ただし、\(O(N^3)\) にしても通る制約にしてあります）。なお、ここで一直線上に乗る点の数を \(4\) 点以上に限定せず、 \(3\) 点や \(2\) 点でも許すことにすると、パターン B の \(5\) 点の候補（風車状ではない方）やパターン C を回収できるので分かりやすいかもしれません。

• パターン A が存在しないか、もしくは \(5\) 点以下だった場合、パターン B のケースがないかを探す（もしパターン A が存在して \(6\) 点以上であれば、それが最大）。特に「風車状」の \(6\) 点配置に注意。\(O(N^3)\) や \(O(N^3/w)\) 時間。

  求め方の詳細

  これはいくつかやり方があります。例えば、

  • 同一直線上に乗るべき \(A,B,C\) の候補を列挙する。これは高々 \(4\binom{N}{2}\) 通りである。なぜなら、 \(1\) つの直線当たり最大 \(4\) 点しか乗っていないので \(3\) 点の選び方は高々 \(4\) 通りだからである。次に、 \(D\) の候補を列挙する。これは高々 \(N-3\) 通り考えられる。最後に、 \(E\) を \(BD\) の延長線上から探し、 \(F\) を \(DA\) または \(DC\) の延長線上から探す。 \(E,F\) が両方見つかるか、片方見つかるか、見つからないかでサイズ \(6,5,4\) の条件を満たす部分集合が検出できる。延長線上から探すのは、 \(BD\) が乗っている直線に対応する配列を見れば定数回の計算で分かるはずなので、 \(O(N^3)\) で解ける。

  • 上の求め方で、\(A,B,C\) を列挙した後で、各点 \(P\) について、\(A,B,P\) の順に並ぶ時の \(B\) としてありうる候補や、\(A,P,C\) の順に並ぶ時の \(A,C\) としてありうる候補を bitset で管理すると、\(D\) の候補が bitwise and を使って求まり、\(O(N^3/w)\) に落ちる。

  • 別の方針として、\(2\) 点の組 \(A,B\) に対して、\(A,B,C\) がこの順に同一直線上に乗るような \(C\) があるかを記録しておく。そして、図 3 の内側の三角形（\(ABD\) あるいは \(BCD\)）を固定し、そこからさらに残り \(3\) 点が選べるか、あるいは \(2\) 点や \(1\) 点が選べるかを判定する。\(O(N^3)\) で判定できる。

• パターン A, B が存在しない場合、パターン C を考える（もしパターン A か B があれば \(4\) 点以上となり、それが最大）。

  求め方の詳細

  パターン A を検出する時に \(l\) 上に 2 点のみが乗るケースも含めれば、パターン C の場合分けは不要になるでしょう。パターン C を別個に判定したいのであれば、全体の点集合の凸包の頂点が元の点集合と一致しているかを確認すれば良いです。一致していれば \(3\) 点以上取れませんし、一致していなければ \(4\) 点取れます。判定には、凸包のアルゴリズムを持ち出さなくても、各点を中心とした偏角ソートの結果を再利用して、180度以上点が存在しない区間があるかどうかを調べる方法もあります。なお、パターン A を求める際に、\(l\) 上に 2 点しか乗っていないケースも含めると、パターン C の場合分けは不要になるかもしれません。

図 1: パターン B における \(5\) 点の取り方①。 \(C\) は \(DE\) 上にあってもなくても良いが、 \(AC\) と \(DE\) が \(A,C\) 以外の交点を持ってはいけない。

図 2: パターン B における \(5\) 点の取り方②。 \(B\) は \(DE\) 上にある必要がある。

図 3: パターン B における \(6\) 点の取り方。風車状の \(6\) 点配置

図 4: パターン B において \(7\) 点がいけない理由の図示。 \(7\) 点目を \(X\) とすると、 \(4\) 点以上が同一直線上に乗らない条件から、 \(X\) は赤線上にあってはいけない。また、それ以外の領域に \(X\) を置くと、青字で書いた \(4\) 点が凸四角形を成す。