P8101 [USACO22JAN] Multiple Choice Test P

· · 题解

P8101 [USACO22JAN] Multiple Choice Test P

对于没见过套路的新手，是好题；对于见多识广的高手，是套路题。

关键结论：可能成为答案的点一定在凸包上。根据 x ^ 2 的凸性容易证明。接下来就好做了。考虑对每组向量均建出凸包，求出这 n 个凸包的闵可夫斯基和，最后用大凸包上的点更新答案。

大小为 a 和大小为 b 的凸包的闵可夫斯基和需要 \mathcal{O}(a + b) 时间计算，因此考虑启发式合并。视向量总数与 n 同级，时间复杂度为 \mathcal{O}(n\log n)。

更为厉害的做法：考虑我们对两个凸包做闵可夫斯基和的过程，就是把所有边拿出来归并排序，再塞回去，这个过程 不改变边本身。因此，我们直接把所有凸包的所有边拿出来，极角排序，再塞回去，就不需要启发式合并的过程了，相当于同时求多个凸包的闵可夫斯基和。时间复杂度也是线性对数，但是比上个做法高妙多了。

代码分别是启发式合并和直接对边排序，后者借鉴了 Benq 在极角排序上的处理。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;

struct Pt {
    int x, y;
    bool operator < (const Pt &rhs) {return x != rhs.x ? x < rhs.x : y < rhs.y;}
    Pt operator + (const Pt &rhs) {return {x + rhs.x, y + rhs.y};}
    Pt operator - (const Pt &rhs) {return {x - rhs.x, y - rhs.y};}
    ll norm() {return 1ll * x * x + 1ll * y * y;}
    ll cross(const Pt &rhs) {return 1ll * x * rhs.y - 1ll * y * rhs.x;}
    void print(string info = "") {cout << info << " " << x << " " << y << endl;}
};

void print(vector <Pt> &v, string info) {
    cout << "print convex hull : " << info << "\n";
    for(auto it : v) cout << it.x << " " << it.y << "\n";
    cout << "finished.\n";
}

ll n, ans;
vector <Pt> c[N]; Pt cen;
set <pair <int, int>> s;
bool cmp(Pt x, Pt y) {
    ll res = (x - cen).cross(y - cen);
    if(res) return res > 0;
    return (x - cen).norm() > (y - cen).norm();
}
void ConvexHull(vector <Pt> &v) {
    static Pt stc[N]; int top = 0;
    for(int i = 1; i < v.size(); i++) if(v[i] < v[0]) swap(v[i], v[0]);
    cen = stc[top = 1] = v[0], sort(v.begin() + 1, v.end(), cmp);
    for(int i = 1; i < v.size(); i++) {
        while(top >= 2 && (stc[top] - stc[top - 1]).cross(v[i] - stc[top]) < 0) top--;
        stc[++top] = v[i];
    } v.clear(), assert(v.size() == 0);
    for(int i = 1; i <= top; i++) v.push_back(stc[i]);
}

vector <Pt> operator + (vector <Pt> &lhs, vector <Pt> &rhs) {
    vector <Pt> ret; ret.push_back(lhs[0] + rhs[0]);
    static Pt sl[N], sr[N]; int pl = 0, pr = 0, L = lhs.size(), R = rhs.size();
    for(int i = 0; i < L; i++) sl[i] = lhs[(i + 1) % L] - lhs[i];
    for(int i = 0; i < R; i++) sr[i] = rhs[(i + 1) % R] - rhs[i];
    while(pl < L && pr < R) ret.push_back(ret.back() + (sl[pl].cross(sr[pr]) > 0 || sl[pl].cross(sr[pr]) == 0 && sl[pl].x > sr[pr].x ? sl[pl++] : sr[pr++]));
    while(pl < L) ret.push_back(ret.back() + sl[pl++]);
    while(pr < R) ret.push_back(ret.back() + sr[pr++]);
    return ret.pop_back(), ret;
}

int main() {
    cin >> n;
    for(int i = 1, k, x, y; i <= n; i++) {
        scanf("%d", &k);
        while(k--) cin >> x >> y, c[i].push_back({x, y});
        ConvexHull(c[i]), s.insert({c[i].size(), i});
    } while(s.size() > 1) {
        int a = s.begin() -> second, b = (++s.begin()) -> second;
        s.erase(s.begin()), s.erase(s.begin());
        c[a] = c[a] + c[b], s.insert({c[a].size(), a});
    } for(auto it : c[s.begin() -> second]) ans = max(ans, it.norm());
    assert(c[s.begin() -> second].size() <= 2e5);
    cout << ans << endl;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;

struct Pt {
    int x, y;
    bool operator < (const Pt &rhs) {return x != rhs.x ? x < rhs.x : y < rhs.y;}
    Pt operator + (const Pt &rhs) {return {x + rhs.x, y + rhs.y};}
    Pt operator - (const Pt &rhs) {return {x - rhs.x, y - rhs.y};}
    ll norm() {return 1ll * x * x + 1ll * y * y;}
    ll cross(const Pt &rhs) {return 1ll * x * rhs.y - 1ll * y * rhs.x;}
    bool dir() {return x > 0 || (x == 0 && y > 0);}
} off[N];

ll n, cnt, ans;
vector <Pt> c; Pt cen, start;
bool cmp(Pt x, Pt y) {
    ll res = (x - cen).cross(y - cen);
    if(res) return res > 0;
    return (x - cen).norm() > (y - cen).norm();
}
void ConvexHull(vector <Pt> &v) {
    static Pt stc[N]; int top = 0;
    for(int i = 1; i < v.size(); i++) if(v[i] < v[0]) swap(v[i], v[0]);
    cen = stc[top = 1] = v[0], sort(v.begin() + 1, v.end(), cmp);
    for(int i = 1; i < v.size(); i++) {
        while(top >= 2 && (stc[top] - stc[top - 1]).cross(v[i] - stc[top]) < 0) top--;
        stc[++top] = v[i];
    } for(int i = (v.clear(), 1); i <= top; i++) v.push_back(stc[i]);
}

int main() {
    cin >> n;
    for(int i = 1, k, x, y; i <= n; i++) {
        scanf("%d", &k), c.clear();
        while(k--) cin >> x >> y, c.push_back({x, y});
        ConvexHull(c), start = start + c[0];
        for(int i = 1; i <= c.size(); i++) off[++cnt] = c[i % c.size()] - c[i - 1];
    }
    sort(off + 1, off + cnt + 1, [&](Pt x, Pt y) {return x.dir() != y.dir() ? x.dir() : x.cross(y) > 0;});
    for(int i = 1; i <= cnt; i++) ans = max(ans, start.norm()), start = start + off[i];
    cout << ans << endl;
    return 0;
}