一句话题意

给你 \(n\) 组向量，从每组中选出一个向量，使被选出的向量的总和到远点的距离最大，\(2\le n \le 2\times 10^5\)。

前置

  1. 凸包
  2. 闵可夫斯基和

解法

结论：所有被选出的向量一定在凸包上。

简单证明：

与原点距离最大的点即为 欧几里得距离 的平方：\(f(p) = x_p^2+y_p^2\)。

显然在凸包上时，距离最大。

我们就可以对每个向量集合求出凸包，然后每次用 闵可夫斯基和 求出凸包的和。

最后遍历凸包上的点，求出最大的距离。

时间复杂度：\(O(n\log n)\)，其中 \(n\) 是向量个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
using db = double;
const int inf = 0x3f3f3f3f;
inline short int sgn(ll x) { return (abs(x) == 0) ? 0 : ((x > 0) ? 1 : -1); } // 判断符号
struct Point {
    ll x, y;
    db ang;  // 极角，用 atan2 计算
    Point operator+(const Point b) const { return {x + b.x, y + b.y}; }
    Point operator-(const Point b) const { return {x - b.x, y - b.y}; }
    ll operator*(const Point b) const { return x * b.y - y * b.x; }
    bool operator<(const Point b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
    bool operator>(const Point b) const { return (y == b.y) ? (x < b.x) : (y > b.y); }
    int Cross(Point a) { return x * a.y - y * a.x; }
    void init() { x = y = 0; }
} sum; // 点
vector<Point> v;
struct Convex {
    vector<Point> p;
    void Andrew() {
        p.clear();
        sort(v.begin(), v.end());
        int n = v.size(), cnt = p.size();
        for (int i = 0; i < n; i++) {
            while (cnt > 1 && ((p[cnt - 1] - p[cnt - 2]) * (v[i] - p[cnt - 1])) <= 0)
                p.pop_back(), cnt--;
            p.push_back(v[i]), cnt++;
        }
        int basic = cnt;
        for (int i = n - 2; i >= 0; i--) {
            while (cnt > basic && sgn(((p[cnt - 1] - p[cnt - 2]) * (v[i] - p[cnt - 1]))) <= 0)
                p.pop_back(), cnt--;
            p.push_back(v[i]), cnt++;
        }
        if (n > 1) p.pop_back();
    } // Andrew 算法实现凸包

    void mincowsky(Convex coh) {
        Point minp{inf, inf};
        int minid = 0, n = coh.p.size();
        for (int i = 0; i < n; i++)
            if (minp > coh.p[i]) minid = i + 1, minp = coh.p[i];

        sum.x += minp.x, sum.y += minp.y;
        for (int j = minid - 1; j > 0; j--) {
            int x = (coh.p[j - 1].x - coh.p[j].x), y = (coh.p[j - 1].y - coh.p[j].y);
            p.push_back(Point{x, y, atan2(y, x)});
        } // 上凸包
        if (n > 0) {
            int x = (coh.p[n - 1].x - coh.p[0].x), y = (coh.p[n - 1].y - coh.p[0].y);
            p.push_back(Point{x, y, atan2(y, x)});
        } // 连接点
        for (int j = n - 1; j >= minid; j--) {
            int x = (coh.p[j - 1].x - coh.p[j].x), y = (coh.p[j - 1].y - coh.p[j].y);
            p.push_back(Point{x, y, atan2(y, x)});
        } // 下凸包
    } // 闵可夫斯基和

} coh, maxcoh; // 凸包
int n;
ll ans;
int main() {
    scanf("%d", &n);
    for (int i = 0,t; i < n; i++) {
        scanf("%d", &t);
        v.resize(t);
        for (int j = 0; j < t; j++)
            scanf("%lld%lld", &v[j].x, &v[j].y);
        coh.Andrew();
        maxcoh.mincowsky(coh);
    }

    sort(maxcoh.p.begin(), maxcoh.p.end(), [](Point a, Point b) { return a.ang > b.ang; }); // 最后按极角排序

    ans = sum.x * sum.x + sum.y * sum.y;
    for (auto p : maxcoh.p) {
        sum.x += p.x, sum.y += p.y;
        ans = max(ans, (sum.x * sum.x + sum.y * sum.y));
    }

    printf("%lld\n", ans);
    return 0;
}