この解説は凸包を上下に分けて求める手法 (Andrew’s monotone chain) の知識を要求します。

柱に (x 座標, y 座標) の辞書順に index を振ります。この時、用いる頂点のうち index が最小・最大のものを固定すると、上側凸包・下側凸包は独立に考えることができます。

最小のものを固定したもとで、上側凸包について以下のような DP を考えます。

\(\mathrm{dp}[i][j] :=\) index が \(j\) 以下の頂点について上側凸包に使うか使わないかが既に定まっており、使う中で最も index が大きいものが \(j\) 、二番目が \(i\) であるときの用いる頂点数の最大値

また遷移について、 \(\mathrm{dp}[i][j]\) から \(j < k\) なる \(k\) について、角 \(i-j-k\) が反時計回りに \(0\) から \(\pi\) の間であるとき、またその時に限り \(\mathrm{dp}[j][k]\) に遷移が行えます。この判定が外積でできることも有名です。

下側凸包も同様の DP ができ、この二つの DP の結果を合わせれば正答を得られます。

この解法は時間計算量 \(\Theta(N^4)\) ですが、 \(1/12\) 倍の定数倍がかかり、適切な実装のもとで十分高速に動作し、少なくとも現在のジャッジでは余裕をもって正解することができます。