解法1 (全探索)

相異なる \(i, j, k\) 全てに対して, \(\angle P_i P_j P_k\) を求めることができれば, 最大値も求めることができる.

ここで, \(\angle P_i P_j P_k\) を求めるために, ベクトルの内積を用いる. \(P_i, P_j, P_k\) を 原点 \(O=(0,0)\) に関する位置ベクトルとみなし, ベクトル \(\boldsymbol{u}, \boldsymbol{v}\) を

\[ \boldsymbol{u}=P_i-P_j, \quad \boldsymbol{v}=P_k-P_j\]

としたとき, 内積に関する式

\[\langle \boldsymbol{u}, \boldsymbol{v} \rangle=|\!|\boldsymbol{u}|\!| |\!| \boldsymbol{v}|\!| \cos \angle P_i P_j P_k\]

から,

\[ \angle P_i P_j P_k={\rm Cos}^{-1} \dfrac{\langle \boldsymbol{u}, \boldsymbol{v} \rangle}{|\!|\boldsymbol{u}|\!| |\!| \boldsymbol{v}|\!|}\]

と求めることができる. 計算量は \(O(N^3)\) になる.

解法2 (偏角ソート)

\(P_j\) を固定する. \(N-1\) 個のベクトル \(\boldsymbol{w}_{j,i}~(i \neq j)\) を \(\boldsymbol{w}_{j,i}:=P_i-P_j\) とする. ここで, \(\boldsymbol{w}_{j,i}\) を偏角の昇順に並び替えた結果を \(\boldsymbol{q}_1, \dots, \boldsymbol{q}_{N-1}\) とし, \(\boldsymbol{q}_m\) の偏角を \(\theta_m~(0 \leq \theta_m < 2\pi)\) とする. ここで, \( \boldsymbol{q}_1, \dots, \boldsymbol{q}_{N-1}\) と \(P_1, \dots, P_{j-1}, P_{j+1}, \dots, P_N\) の間には1対1の対応があることに注意すること.

\(\boldsymbol{q}_m\) を一つ選び, \(\boldsymbol{q}_m=P_i-P_j\) とする. ここで, \(i,j\) を固定したときに, \(\angle P_i P_j P_s\) を最大にする \(s\) の可能性があるのは, 以下で記した2つに限ることがわかる.

\(\theta_{l} \leq \theta_m \pm \pi \leq \theta_{l+1}\) となるような \(l\) が \(\pm\) を適切に選ぶことにより, 必ず存在するが, このとき, 上で述べた \(s\) は \(l, l+1\) の2つに限る. ただし, 添字について, \(N\) と \(1\) は同一視する.

以上の工程について, \(i,j\) を固定して \(l\) 求めるために二分探索を利用して, \(O(\log N)\) で求められ, 全体で \(O(N^2 \log N)\) である. この計算量は \(N \leq 2000\) という制約下では高速である.