Engines [AtCoder Beginner Contest 139 F]

https://atcoder.jp/contests/abc139/tasks/abc139_f

前提知識

• 幾何問題

解説

https://atcoder.jp/contests/abc139/submissions/7340335

頂点全てを偏角ソートすると、最適な組み合わせは、連続する区間の頂点を選んで選択することである。
言われてみればそんな気もするが、これを無からひっぱり出してくるのは難しい。
とりあえず、こういうパターンもあると覚えておくことにする。
ここまでの考察で600点ある。

あとは、偏角ソートして、区間を足していけばいい。
愚直にやっても(N³)となるが、順次足し合わせていくとO(N²)となり、
思いつけばこっちのほうが簡単なので、これでやるとAC

ついでに2点間偏角ソートという応用もある。
気になる人は幾何問題に問題がある。

int N;
//---------------------------------------------------------------------------------------------------
void _main()
{
    cin >> N;
    vector<P> v;
    rep(i, 0, N)
    {
        int x, y;
        cin >> x >> y;
        if(x != 0 or y != 0) {
            v.push_back(P(x, y));
        }
    }

    sort(all(v), [&](P a, P b) { return argument(P(0, 0), a) < argument(P(0, 0), b); });

    double ans = 0;
    int n = v.size();
    rep(i, 0, n) {
        double x = 0, y = 0;
        rep(j, 0, n) {
            auto p = v[(i + j) % n];
            x += real(p);
            y += imag(p);

            chmax(ans, sqrt(x * x + y * y));
        }
    }
    printf("%.10f\n", ans);
}