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 <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <stdbool.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class Point {
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) { return Point(x+p.x, y+p.y); }
    Point operator - (Point p) { return Point(x-p.x, y-p.y); }
    Point operator * (double a) { return Point(a*x, a*y); }
    Point operator / (double a) { return Point(x/a, y/a); }

    double abs() {return sqrt(norm()); }
    double norm() {return x*x + y*y; }
};

typedef Point Vector;

double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {
    return a.x*b.y - a.y*b.x;
}

Vector normal(Point p0, Point p1); //ベクトルp0p1の法線ベクトル
int argmax(const vector<double> &v); //std::vectorのargmax関数

int main(){
    #if 0
    std::ifstream in("in21.txt");
    std::cin.rdbuf(in.rdbuf());
    #endif

    int n;
    cin >> n;
    vector<Point> data(n);

    for(int i=0; i<n; i++){
        cin >> data[i].x >> data[i].y;
    }

    Point p0, p1;
    Vector nv;
    vector<double> xNormalNoDup(0);
    vector<Vector> normalVector(0);
    xNormalNoDup.reserve(n);
    normalVector.reserve(n);
    map<double, int> isSwitchVertex;
    map<double, int> isSwitchVertex0;
    map<double, int> isSwitchVertex1;

    for(int i=0; i<n; i++){
        p0 = data[i];
        p1 = data[(i+1)%n];
        nv = normal(p0, p1);
        normalVector.push_back(nv);
        if (nv.y > 0 || nv.x == 1){
            isSwitchVertex0[ nv.x ] += 1;
            isSwitchVertex[ nv.x ] = 0;
        }
        else{
            isSwitchVertex1[ -nv.x ] += 1;
            isSwitchVertex[ -nv.x ] = 0;
        }
    }

    //Extract keys of isSwitchVertex and sort
    for(map<double,int>::iterator it = isSwitchVertex.begin(); it != isSwitchVertex.end(); ++it) {
        xNormalNoDup.push_back(it->first);
    }
    sort(xNormalNoDup.begin(), xNormalNoDup.end(), greater<double>() );

    //find the first pair
    int pairIndex0 = -1; //upside
    int pairIndex1 = -1; //downside
    int change0, change1;
    Vector nv0, nv1;
    for(int i=0; i<n; i++){
        nv0 = normalVector[i];
        nv1 = normalVector[(i+1)%n];
        if( nv0.y<0 && nv1.y>=0 ) pairIndex0 = (i+1)%n;
        if( nv0.y>0 && nv1.y<=0 ) pairIndex1 = (i+1)%n;
    }
    if(pairIndex0<0 || pairIndex1<0) cout << "ERROR: Pair Initialization failed.";
    //cout << "First Pair" << " " << pairIndex0 << " " << pairIndex1 << endl;

    double maxDiameter = ( data[pairIndex0] - data[pairIndex1] ).abs();
    double diameter = 0;

    for(int i=0; i<xNormalNoDup.size(); i++){
        change0 = isSwitchVertex0[ xNormalNoDup[i]];
        change1 = isSwitchVertex1[ xNormalNoDup[i]];
        //cout << "flag:" << change0 << " " << change1 << " ";
        pairIndex0 += change0;
        pairIndex1 += change1;
        pairIndex0 %= n;
        pairIndex1 %= n;
        diameter = ( data[pairIndex0] - data[pairIndex1] ).abs();
        //if(diameter > maxDiameter) cout << pairIndex0 << " " << pairIndex1 << " " << diameter << endl;
        maxDiameter = (diameter > maxDiameter)? diameter: maxDiameter;
        //cout << pairIndex0 << " " << pairIndex1 << " " << maxDiameter << endl;
    }

    cout << setprecision(14) << maxDiameter << endl;

    return 0;
}

Vector normal(Point p0, Point p1){
    Vector nv;
    nv.x = - ( p1.y - p0.y );
    nv.y = p1.x - p0.x;
    double a = nv.abs();
    return nv / a;
}

int argmax(const vector<double> &v){
    return distance(v.begin(), max_element(v.begin(), v.end()));
}