题解

#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;
}