ABC139 F. Engines

問題

N個の2次元ベクトルが与えられる。
ここからいくつか選んだ和のベクトルの大きさの最大値を求めよ。

制約

• 1 <= N <= 100
• -1,000,000 <= x_i, y_i <= 1,000,000

解法

答えとなるベクトルの向きを固定して考える。
このとき、この向きに寄与するベクトルは、その向きの成分が正となるベクトル(±90度までにあるベクトル)だけを集めてきたときの和になる。

なので、角度でベクトルをソートし、角度が180度分の範囲にあるベクトルをすべて足し合わせた中で一番大きさが大きくなるものを答えればよい。

または、より簡単に、連続区間をすべてチェックしても間に合うので、O(n^2)またはO(n^3)でもよい。