凸包の辺は傾きが単調であることに着目します。

点対 \((i, j)\) \((1 \leq i, j \leq N, i \neq j)\) を線分 \(i-j\) の傾きの昇順に並び替えておくと、以下のような DP が動作します。

1. 始点 \(s\) を固定する
2. \(\mathrm{dp}[s]\) を \(0\) に、他を \(\infty\) に初期化する
3. 点対 \((i, j)\) の傾きの昇順に次の遷移を行う
   • \(\mathrm{dp}[j] \leftarrow \max(\mathrm{dp}[j], \mathrm{dp}[i] + 1)\)

ただし、 \(\mathrm{dp}[s]\) への遷移では代わりに答えを更新することにします。

これにより、元の点に戻ってくる傾き昇順のルートが全て尽くされ、この問題を \(\Theta(N^3)\) で解くことができました。