MnZn 求助闵可夫斯基和
查看原帖
MnZn 求助闵可夫斯基和
420129
Nt_Tsumiki楼主2024/10/18 21:46

rt

只能过 m2m\le 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;
}
2024/10/18 21:46
加载中...