公式解説と同様の考察により，本問題は，与えられた \(N\) 個の2次元ベクトルから \(k\) 個選んでそれらの総和のノルムを最大化する問題に帰着できます．

\(k=1\) に対する答えは容易に求まります．そうでない場合を考えます．あらかじめ，各座標成分に小さな乱数を加えておくことで，どの3点も同一直線上にないとしてよいです．

\(k\) を固定して考えると，最適な点の選び方において，選ばれた点と選ばれなかった点を分離する直線が存在します．なぜならば，進む方向のベクトル \(v\) を決めると，そのベクトルとの内積が大きいものの上位 \(k\) 個を選ぶのが最適であり， \(v\) を法線ベクトルとして持つような直線により分離できるからです．

選ばれる点の集合を不変に保ちながら，この直線を連続的に移動させることで，次のいずれかが成り立つようにできます．

• 直線上に，選ばれた点が2点ある
• 直線上に，選ばれなかった点が2点ある

よって，2点を通る \(N(N-1)/2\) 本の直線を全探索し，どちらの側を選ぶかを両方試すことで，答えを求めることができます．これは，1点を固定してそれを中心として他の点を偏角ソートし，直線上のもう1点を選ぶ尺取り法を行うことで \(O(N^2 \log N)\) 時間で実行可能です．

実装例 (C++)