rt
只能过 m≤2 的部分,怀疑是闵可夫斯基和板子写挂了。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define N 200005
#define LL long long
inline int R() {
int x=0; bool f=0; char c=getchar();
while (!isdigit(c)) f|=(c=='-'),c=getchar();
while (isdigit(c)) x=x*10+c-'0',c=getchar();
return f?-x:x;
}
template<typename T>
void W(T x,int op=0) {
if (x<0) return putchar('-'),W(-x,op);
if (x>9) W(x/10); putchar(x%10+'0');
if (op) putchar(op==1?' ':'\n');
}
using namespace std;
int n,m;
namespace CG {
const long double eps=1e-11;
template<typename T> struct Poi {
T x,y;
Poi(T _x=0,T _y=0) { x=_x,y=_y; }
bool operator==(const Poi tmp) const { return x==tmp.x and y==tmp.y; }
Poi operator+(const Poi tmp) const { return Poi(x+tmp.x,y+tmp.y); }
Poi operator-(const Poi tmp) const { return Poi(x-tmp.x,y-tmp.y); }
};
template<typename T> inline T Cro(Poi<T> x,Poi<T> y) { return x.x*y.y-x.y*y.x; }
template<typename T> inline T Dot(Poi<T> x,Poi<T> y) { return x.x*y.x+x.y*y.y; }
template<typename T> struct Con {
vector<Poi<T> > p;
inline void push_back(Poi<T> x) { p.push_back(x); }
inline void pop_back() { p.pop_back(); }
inline Poi<T> back() { return p.back(); }
inline Poi<T> seback() { return p[p.size()-2]; }
inline size_t size() { return p.size(); }
inline void resize(int n,Poi<T> x=Poi<T>(0,0)) { p.ressize(n,x); }
inline Poi<T> &operator[](int x) { return p[x]; }
};
template<typename T>
inline Con<T> getCon(int n,Poi<T> *p) {
Con<T> con;
sort(p+1,p+n+1,[](Poi<T> tmp1,Poi<T> tmp2) {
return tmp1.x^tmp2.x?tmp1.x<tmp2.x:tmp1.y<tmp2.y;
});
for (int i=1;i<=n;i++) {
while (con.size()>1 and Cro(con.back()-p[i],con.seback()-p[i])<=0)
con.pop_back();
con.push_back(p[i]);
}
int tmp=con.size();
for (int i=n-1;i;i--) {
while (con.size()>tmp and Cro(con.back()-p[i],con.seback()-p[i])<=0)
con.pop_back();
con.push_back(p[i]);
}
con.pop_back();
return con;
}
template<typename T>
inline Con<T> Minkowski(Con<T> con1,Con<T> con2) {
int n=con1.size(),m=con2.size();
auto tmp1=con1[n-1],tmp2=con2[m-1];
for (int i=n-1;i;i--) con1[i]=con1[i]-con1[i-1];
for (int i=m-1;i;i--) con2[i]=con2[i]-con2[i-1];
con1.push_back(con1[0]-tmp1),con2.push_back(con2[0]-tmp2);
Con<T> con3;
int i=1,j=1;
while (i<=n and j<=m) {
if (Cro(con1[i],con2[j])>0 or (Cro(con1[i],con2[j])==0 and con1[i].x>con2[j].x)) con3.push_back(con1[i++]);
else con3.push_back(con2[j++]);
}
while (i<=n) con3.push_back(con1[i++]);
while (j<=m) con3.push_back(con2[j++]);
int k=con3.size(); Con<T> con4;
con4.push_back(con1[0]+con2[0]);
for (int i=0;i<k-1;i++) con4.push_back(con3[i]+con4.back());
return con4;
}
} using CG::Poi,CG::Con;
Poi<LL> p[N]; Con<LL> con[N],ans;
Con<LL> sol(int l,int r) {
if (l==r) return con[l];
int mid=(l+r>>1);
return CG::Minkowski(sol(l,mid),sol(mid+1,r));
}
int main() {
n=R();
for (int i=1;i<=n;i++) {
m=R();
for (int j=1;j<=m;j++)
p[j].x=R(),p[j].y=R();
con[i]=CG::getCon(m,p);
}
ans=sol(1,n); LL Ans=0;
for (int i=0;i<ans.size();i++)
Ans=max(Ans,1ll*ans[i].x*ans[i].x+ans[i].y*ans[i].y);
W(Ans,2);
return 0;
}