Problem: Find the diameter of a convex polygon g. In other words, find a pair of points that have maximum distance between them.

Constraints

* 3 ≤ n ≤ 80000
* -100 ≤ xi, yi ≤ 100
* No point in the g will occur more than once.

Input


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points in g.

In the following lines, the coordinate of the i-th point pi is given by two real numbers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the diameter of g in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

3
0.0 0.0
4.0 0.0
2.0 2.0


Output

4.00


Input

4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0


Output

1.414213562373

Solution (in CPP):

Solution:

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const ll maxn=1e4+200;
const int inf=0x3f3f3f3f;
const double EPS=1e-10;
//typedef pair<int,int> PA;
double add(double a,double b){//考虑误差的加法运算
    if(abs(a+b)<EPS*(abs(a)+abs(b))) return  0;
    return a+b;
}
int sgn(double x){
    if(abs(x)<EPS)  return 0;
    if(x<0) return -1;
    else return 1;
}
class Point{
public:
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){
    }
    Point operator+ (Point p){
        return Point(add(x,p.x),add(y,p.y));
    }
    Point operator -(Point p){
        return Point(add(x,-p.x),add(y,-p.y));
    }
    Point operator *(double d){
        return Point(x*d,y*d);
    }
    double operator *(Point p){
        return add(x*p.x,y*p.y);//外积
    }
    double operator ^(Point p){//内积
        return add(x*p.y,-y*p.x);
    }
    double det(Point p){
     return add(x*p.y,-y*p.x);
    }
    double len(){
        return sqrt(add(x*x,y*y));
    }
};
double dist(Point p1,Point p2)//距离的平方
{
    return add((p1.x-p2.x)*(p1.x-p2.x),(p1.y-p2.y)*(p1.y-p2.y));
}
class Line{
public:
    Point s,e;
    Line(){}
    Line(Point s,Point e):s(s),e(e){}
};
bool onSge(Line l,Point q){
    return ((l.s-q)^(l.e-q))==0&&((l.s-q)*(l.e-q))<=0;
}
Point operator *(double d,Point p){
    return Point(p.x*d,p.y*d);
}
Point getProject(Point p1,Point p2,Point q){//q 在直线p1,p2上的投影坐标
    double d1=1.0/(p2-p1).len();
    Point ans=(q-p1)*(p2-p1)*(p2-p1)*d1*d1;
    return ans+p1;
}
Point getReflect(Point p1,Point p2,Point q){//q 关于直线p1 p2的 反射坐标
    return 2.0*getProject(p1,p2,q)-q;
}
double getDisPP(Point a,Point b){//两点之间距离
    return (b-a).len();
}
double getDisPL(Line l,Point p){//点到直线距离
    Point x=getProject(l.s,l.e,p);
    return (p-x).len();
}
double getDisPS(Line l,Point p){//点到线段最短距离
    Point x=getProject(l.s,l.e,p);
    if(onSge(l,x))
        return (x-p).len();
    else
        return min((p-l.s).len(),(p-l.e).len());

}
double getDisSS(Line la,Line lb){//保证两线段不相交 isInterSS==false
    return min(min(getDisPS(la,lb.s),getDisPS(la,lb.e)),
			min(getDisPS(lb,la.s),getDisPS(lb,la.e)));
}

int getDirPPP(Point p,Point p1,Point p2){
    return sgn((p1-p)^(p2-p));//1代表 p2在p1的逆时针方向  0共线 ，-1是p2在p1的顺时针方向
}
/*
1 逆时针
2 顺时针
3 在p->p1的后面
4 在p->p1的前面
5 在p->p1上
*/
int getStatePP(Point p,Point p1,Point p2){//返回 p2 关于p 在p1的什么方向
        int a=sgn((p1-p)^(p2-p));
        int b=sgn((p1-p)*(p2-p));
        if(a>0){//
            return 1;
        }
        else if(a<0){
            return 2;
        }
        else if(b<0){
            return 3;
        }
        else if(b>0&&sgn((p1-p)*(p2-p1))>0){
            return 4;
        }
        else{
           return 5;
        }
        return 0;
}
bool isInterSS(Line la,Line lb){//线段是否想交
    int d1=getDirPPP(lb.s,lb.e,la.s);
    int d2=getDirPPP(lb.s,lb.e,la.e);
    int d3=getDirPPP(la.s,la.e,lb.s);
    int d4=getDirPPP(la.s,la.e,lb.e);
    if(d1*d2<0&&d3*d4<0)
        return true;
    else if(d1==0&&onSge(lb,la.s))
        return true;
    else if(d2==0&&onSge(lb,la.e))
        return true;
    else if(d3==0&&onSge(la,lb.s))
        return true;
    else if(d4==0&&onSge(la,lb.e))
        return true;
    else
        return false;

}
int getStateLL(Line la,Line lb){//两个直线 垂直，相交或者平行
    if(sgn((la.e-la.s)^(lb.e-lb.s))==0){
        return 2;//平行
    }//两向量平行 内积为0
    else if(sgn((la.e-la.s)*(lb.e-lb.s))==0){
        return 1;//垂直
    }
    else return 0;
}
typedef Point P;
Point getInterLL(Point p1,Point p2,Point q1, Point q2){//得到直线交点
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}
double getAreaPolygon(Point p[],int n){//下标从0开始  计算多边形面积
    double res=0.0;
    for(int i=0;i<n;++i)
        res+=(p[i]^p[(i+1)%n])/2;
    return res;
}
Point PA[110000];

bool _cmp(Point p1,Point p2)//相对于pa[0]的
{
    double tmp=(p1-PA[0])^(p2-PA[0]);
    if(sgn(tmp)>0) return true;
    else if(sgn(tmp)==0 &&sgn((PA[0]-p1).len()-(PA[0]-p2).len())<=0)//如果奇角相同 距离近的排在前面
        return true;
    else return false;
}
void sortPolarAngle(Point PA[],int n)//对数组进行极角排序  点将逆时针排序 WA
{
    Point p0=PA[0];
    int k=0;
    /* 找到最下边的一个点 靠左的一个点*/
    for(int i=1;i<n;++i){
        if((p0.y>PA[i].y)||(p0.y==PA[i].y&&p0.x>PA[i].x))
        {
            p0=PA[i];
            k=i;
        }
    }
    swap(PA[k],PA[0]);
    sort(PA+1,PA+n,_cmp);
    return ;
}
//判断是否为凸包
//允许共线边
//点可以是顺时针给出也可以是逆时针给出
//点的编号为0~n-1
bool isConvex(Point poly[],int n)
{
    bool s[3];
    memset(s,0,sizeof(s));
    for(int i=0;i<n;++i){
        s[sgn( (poly[(i+1)%n]-poly[i]) ^ (poly[(i+2)%n]-poly[i]) )+1]=true;
        if(s[0]&&s[2]) return false;//拐的方向不同
    }
    return true;
}

//Gragham扫描法求凸包
//输入: 多边形和顶点个数
//得到的凸包的点最少，逆时针给出，第一个点是最靠左其次下的点。
bool cmp_x(const Point &p,const Point &q)
{
    if(p.x!=q.x) return p.x<q.x;
    return p.y<q.y;
}
vector<Point> convex_hull(Point *ps,int n)
{
    sort(ps,ps+n,cmp_x);
    int k=0; //凸包的顶点数
    vector<Point> qs(n*2); //构造中的凸包
    //构造凸包下侧
    for(int i=0; i<n;++i){
        while(k>1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    //构造凸包的上侧
    for(int i=n-2,t=k;i>=0;--i){
        while(k>t && (qs[k-1] - qs[k-2] ).det(ps[i]-qs[k-1]) <= 0 ) k--;
        qs[k++]=ps[i];
    }
    qs.resize(k-1);
    return qs;
}
//旋转卡壳求平面最远点对
//输入: 多边形和顶点个数
//输出: 最远点对距离的平方
//
double rotaing_calipers(P* ps,int pn)
{
    vector<P> qs(ps,ps+pn);
    int n=qs.size();
    if(n==2){
        return  dist(qs[0], qs[1]);
    }
    int j=1;
    double ans=0.0;
    for(int i=0;i<n;++i)
    {
        while( (qs[(i+1)%n]-qs[i]).det( qs[(j+1)%n] - qs[j]) >=0 ) j=(j+1)%n;
        ans=max(ans, max(dist(qs[j],qs[i]), dist(qs[j],qs[(i+1)%n] )) );
    }
    return ans;
}
//Point PA[110000];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&PA[i].x,&PA[i].y);
    }
    double res=rotaing_calipers(PA,n);
    printf("%.10f\n",sqrt(res) );
    return 0;
}


/*

//这样得到的是在凸包上最多的点,第一个点是最下左的点,且逆时针给出.
bool cmp_y(const Point &p,const Point &q)
{
    //找到y坐标最小,相等时x坐标最小排在前面
    if(p.y!=q.y) return p.y<q.y;
    return p.x<q.x;
}

vector<Point> convex_hull(Point *ps,int n)
{
    sort(ps,ps+n,cmp_y);
    int k=0; //凸包的顶点数
    vector<Point> qs(n*2); //构造中的凸包
    //构造凸包下侧
    for(int i=0; i<n;++i){
        while(k > 1 && sgn( (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) ) < 0) k--;
        qs[k++] = ps[i];
    }
    //构造凸包的上侧
    for(int i=n-2,t=k;i>=0;--i){
        while(k > t && sgn( (qs[k-1] - qs[k-2] ).det(ps[i]-qs[k-1]) ) < 0 ) k--;
        qs[k++]=ps[i];
    }
    qs.resize(k-1);
    return qs;
}
*/