#include #define whole(xs) xs.begin(),xs.end() using namespace std; namespace { typedef double real; typedef long long ll; const real EPS = 1e-8; template ostream& operator<<(ostream& os, const vector& vs) { if (vs.empty()) return os << "[]"; auto i = vs.begin(); os << "[" << *i; for (++i; i != vs.end(); ++i) os << " " << *i; return os << "]"; } template istream& operator>>(istream& is, vector& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } struct Point { ll x, y; int index; Point() {} Point(ll x, ll y) : x(x), y(y) {} Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); } Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); } static bool compX(const Point& a, const Point& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } static bool compY(const Point& a, const Point& b) { return a.y == b.y ? a.x < b.x : a.y < b.y; } }; istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; } ostream& operator<<(ostream& os, const Point& p) { return os << "Point(" << p.x << "," << p.y << ")"; } struct Node { Node* parent; shared_ptr left, right; ll left_x, right_x; vector ys; }; ostream& operator<<(ostream& os, const Node& node) { return os << "( [" << node.left_x << "," << node.right_x << "] -> " << node.ys; } shared_ptr construct(vector::iterator lb, vector::iterator ub) { auto n = make_shared(); n->left_x = lb->x; n->right_x = (ub - 1)->x; if (ub - lb == 1) { n->ys.clear(); n->ys.push_back(*lb); return n; } auto mid = lb + (ub - lb) / 2; auto l = construct(lb, mid), r = construct(mid, ub); l->parent = n.get(); r->parent = n.get(); n->left = l; n->right = r; size_t li = 0, ri = 0; while (true) { if (li >= l->ys.size() && ri >= r->ys.size()) break; if (li >= l->ys.size()) n->ys.push_back(r->ys[ri++]); else if (ri >= r->ys.size()) n->ys.push_back(l->ys[li++]); else { n->ys.push_back( l->ys[li].y < r->ys[ri].y ? l->ys[li++] : r->ys[ri++] ); } } return n; } void query(shared_ptr root, ll sx, ll sy, ll gx, ll gy, vector& result) { if (gx < root->left_x || root->right_x < sx) { // do nothing; } else if (sx <= root->left_x && root->right_x <= gx) { auto& ys = root->ys; auto lb = upper_bound(whole(ys), Point(0, sy - 1), Point::compY); auto ub = lower_bound(whole(ys), Point(0, gy + 1), Point::compY); result.insert(result.end(), lb, ub); } else { query(root->left, sx, sy, gx, gy, result); query(root->right, sx, sy, gx, gy, result); } } struct UnionFind { int N; vector P; UnionFind(int N) : N(N) { P.clear(); P.resize(N, -1); } int root(int x) { if (P[x] == -1) return x; return P[x] = root(P[x]); } int query(int x, int y) { return root(x) == root(y); } void merge(int x, int y) { x = root(x); y = root(y); if (x == y) return; P[x] = y; } }; real dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; } real cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; } real norm(const Point& a) { return sqrt(dot(a, a)); } int ccw(Point a, Point b, Point c){ b = b - a; c = c - a; if (cross(b, c) > EPS) return +1; if (cross(b, c) < -EPS) return -1; if (dot(b, c) < 0) return +2; if (norm(b) < norm(c)) return -2; return 0; } void convexHull(vector ps, vector& ans) { assert(ps.size() >= 3); sort(ps.begin(), ps.end(), Point::compX); int N = ps.size(); int k = 0; ans.resize(N * 2); for (int i = 0; i < N; ans[k++] = ps[i++]) while (k >= 2 && ccw(ans[k - 2], ans[k - 1], ps[i]) <= 0) k--; for (int i = N - 2, t = k + 1; i >= 0; ans[k++] = ps[i--]) while (k >= t && ccw(ans[k - 2], ans[k - 1], ps[i]) <= 0) k--; ans.resize(k - 1); } int next(const vector& P, int i) { int N = P.size(); return (i + 1) % N; } // from http://www.prefield.com/algorithm/geometry/convex_diameter.html real farthest(const vector& P) { const int n = P.size(); int is = 0, js = 0; for (int i = 1; i < n; i++) { if (P[i].y > P[is].y) is = i; if (P[i].y < P[js].y) js = i; } real maxd = norm(P[is] - P[js]); int i, maxi, j, maxj; i = maxi = is; j = maxj = js; do { if (cross(P[next(P, i)] - P[i], P[next(P, j)] - P[j]) >= 0) j = (j + 1) % n; else i = (i + 1) % n; if (norm(P[i] - P[j]) > maxd) { maxd = norm(P[i] - P[j]); maxi = i; maxj = j; } } while (i != is || j != js); return maxd; /* farthest pair is (maxi, maxj). */ } int N; vector P; void input() { cin >> N; P.clear(); P.resize(N); for (int i = 0; i < N; i++) { cin >> P[i]; P[i].index = i; } } ll dist_sq(const Point& a, const Point& b) { ll dx = a.x - b.x; ll dy = a.y - b.y; return dx * dx + dy * dy; } void solve() { vector ps = P; sort(ps.begin(), ps.end(), Point::compX); auto root = construct(ps.begin(), ps.end()); UnionFind uf(N); for (int i = 0; i < N; i++) { int x = P[i].x, y = P[i].y; vector ns; query(root, x - 10, y - 10, x + 10, y + 10, ns); for (auto n : ns) { if (P[i].index == n.index) continue; if (dist_sq(n, P[i]) <= 100) { uf.merge(P[i].index, n.index); } } } real ans = 0; vector used(N, false); for (int i = 0; i < N; i++) { if (used[i]) continue; vector vs; for (int j = i; j < N; j++) { if (uf.query(i, j)) { vs.push_back(P[j]); used[j] = true; } } if (vs.size() == 1) { // do nothing } else if (vs.size() == 2) { ans = max(ans, norm(vs[0] - vs[1])); } else { vector hull; convexHull(vs, hull); ans = max(ans, farthest(hull)); } } cout << fixed << setprecision(12) << ans + 2 << endl; } } int main() { input(); solve(); return 0; }