CF1841F Monocarp and a Strategic Game

Kidding_Ma · 2023-06-14 12:24:36 · 题解

题意抽象为在 n 个 a_i,b_i,c_i,d_i 中取 k 个 a_i,b_i,c_i,d_i，k 为任意数。

然后求最大的 \sum\limits_{j=1}^{k} a_{j}^{2}+b_{j}^{2}-2a_{j}b_{j}+c_{j}^{2}+d_{j}^{2}-2c_{j}d_{j}，记 \vec{p_j}=(b_j-a_j,d_j-c_j)，则题意转化为计算几何问题，取 k 个向量求最大 \sum p_j。

发现是原题，双倍经验。

先极角排序，发现选连续的一段点一定是最优的。

实现上对每个向量取关于原点对称向量后，极角排序。复杂度 O(n\log n)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Real = double;
using Point = complex<Real>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        p[i] = Point(b - a, d - c);
    }

    vector<pair<double, int>> a;
    Point res;
    for (int i = 0; i < n; i++) {
        double a1 = arg(p[i]);
        double a2 = arg(-p[i]);
        a.push_back({a1, i + 1});
        a.push_back({a2, -(i + 1)});
        if (a1 > a2) {
            res += p[i];
        }        
    }

    sort(a.begin(), a.end());

    double ans = 0;
    for (auto &[_, v] : a) {
        if (v < 0) {
            res -= p[-v - 1];
        } else {
            res += p[v - 1];
        }
        ans = max(ans, norm(res));
    }
    cout << fixed << setprecision(15) << ans << '\n';

    return 0;
}