求个凸包，然后在凸包上求：
时间复杂度大概是 O（nlogn+n）：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;

const double eps=1e-8;
const double dnf=1e20;
const double pi=acos(-1.0);
const int maxp=51010;

struct Point
{
    int x,y;
    Point(){}
    Point(int xx,int yy)
    {
        x=xx,y=yy;
    }

    void input(void)
    {
        scanf("%d%d",&x,&y);
    }
    void output(void)
    {
        printf("%d %d\n",x,y);
    }

    bool operator == (const Point &b) const
    {
        return x==b.x&&y==b.y;
    }

    bool operator < (const Point &b) const
    {
        if(x!=b.x) return x<b.x;
        else return y<b.y;
    }

    Point operator + (const Point &b) const
    {
        return Point(x+b.x,y+b.y);
    }

    Point operator - (const Point &b) const
    {
        return Point(x-b.x,y-b.y);
    }

    Point operator * (const double &k) const
    {
        return Point(x*k,y*k);
    }

    Point operator / (const double &k) const
    {
        return Point(x/k,y/k);
    }

    int operator ^ (const Point &b) const
    {
        return x*b.y-y*b.x;
    }

    int operator * (const Point &b) const
    {
        return x*b.x+y*b.y;
    }


    int len2(void)
    {
        return x*x+y*y;
    }


    int dis(const Point &b) const
    {
        return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
    }

};

double cross(Point A,Point B,Point C)
{
    return (B-A)^(C-A);
}

struct polygon
{
    int n;
    Point p[maxp];

    void input(int nn)
    {
        n=nn;
        for(int i=0;i<n;i++)
            p[i].input();
    }


    struct cmp
    {
        Point p;
        cmp(const Point &p0) { p=p0;}
        bool operator()(const Point &aa,const Point &bb)
        {
            Point a=aa,b=bb;
            int d=(a-p)^(b-p);
            if(d==0)
                return a.dis(p)-b.dis(p)<0;
            return d>0;
        }
    };

    void norm(void)
    {
        Point mi=p[0];
        for(int i=1;i<n;i++) mi=min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }

    void get_convex(polygon &convex)
    {
        sort(p,p+n);
        convex.n=n;
        for(int i=0;i<min(n,2);i++)
            convex.p[i]=p[i];
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
        if(n<=2) return ;
        int &top=convex.n;
        top=1;
        for(int i=2;i<n;i++)
        {
            while(top&&((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
        int temp=top;
        convex.p[++top]=p[n-2];
        for(int i=n-3;i>=0;i--)
        {
            while(top!=temp&&((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
        convex.norm();

    }

    void get_convex_graham(polygon &convex)
    {
        norm();
        int &top=convex.n;
        top=0;
        if(n==1)
        {
            top=1;
            convex.p[0]=p[0];
            return ;
        }
        if(n==2)
        {
            top=2;
            convex.p[0]=p[0];
            convex.p[1]=p[1];
            if(convex.p[0]==convex.p[1]) top--;
            return ;
        }

        convex.p[0]=p[0];
        convex.p[1]=p[1];
        top=2;
        for(int i=2;i<n;i++)
        {
            while(top>1&&((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0)
                top--;
            convex.p[top++]=p[i];
        }
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
    }

    int farthest_pair(void)
    {
        int ans=0;
        p[n]=p[0];
        int now=1;
        for(int i=0;i<n;i++)
        {
            while(cross(p[i],p[i+1],p[now])<cross(p[i],p[i+1],p[now+1]))
                now=(now+1)%n;
            ans=max(ans,max(p[i].dis(p[now]),p[i+1].dis(p[now])));
            //ans=max(ans,p[i].dis(p[now])); 也可以
        }
        return ans;

    }

};


int main(void)
{
    int n;
    scanf("%d",&n);
    polygon p,q;
    p.input(n);
    p.get_convex(q);
    printf("%d\n",q.farthest_pair());
    return 0;
}