import std.algorithm; import std.array; import std.ascii; import std.container; import std.conv; import std.math; import std.numeric; import std.range; import std.stdio; import std.string; import std.typecons; void log(A...)(A arg) { stderr.writeln(arg); } int size(T)(in T s) { return cast(int)s.length; } const EPS = 1e-7; struct Point { long x, y; int index; Point opBinary(string op)(in Point p) const if (op == "+" || op == "-") { return Point(mixin("x" ~ op ~ "p.x"), mixin("y" ~ op ~ "p.y")); } }; class RangeTree { class Node { Node parent; Node left, right; long left_x, right_x; Point[] ys; override string toString() const { return format("([%s,%s] -> %s)", left_x, right_x, ys); } } Node construct(Point[] ps) { auto n = new Node; n.left_x = ps.front.x; n.right_x = ps.back.x; if(ps.length <= 1024) { n.ys = ps.dup.sort!"a.y < b.y".array; return n; } auto l = construct(ps[0 .. $ / 2]); auto r = construct(ps[$ / 2 .. $]); l.parent = n; r.parent = n; n.left = l; n.right = r; auto li = 0, ri = 0; while (true) { if (li >= l.ys.length && ri >= r.ys.length) break; if (li >= l.ys.length) n.ys ~= r.ys[ri++]; else if (ri >= r.ys.length) n.ys ~= l.ys[li++]; else { n.ys ~= (l.ys[li].y < r.ys[ri].y ? l.ys[li++] : r.ys[ri++]); } } return n; } Node root; this(Point[] ps) { ps.sort!"a.x < b.x"; this.root = construct(ps); } /* (sx <= x <= gx && sy <= y <= gy)なる点(x, y)をresultに入れる. 閉区間なの注意 */ Point[] query(long sx, long sy, long gx, long gy) { Point[] result; void f(Node cur_root) { if (gx < cur_root.left_x || cur_root.right_x < sx) { // do nothing } else if (sx <= cur_root.left_x && cur_root.right_x <= gx) { auto ys = cur_root.ys; result ~= ys.assumeSorted!"a.y < b.y".upperBound(Point(0, sy - 1)).lowerBound(Point(0, gy + 1)).array; } else { if(cur_root.left is null || cur_root.right is null) { foreach (p; cur_root.ys.assumeSorted!"a.y < b.y".upperBound(Point(0, sy - 1)).lowerBound(Point(0, gy + 1))) { if (sx <= p.x && p.x <= gx && sy <= p.y && p.y <= gy) { result ~= p; } } } else { f(cur_root.left); f(cur_root.right); } } } f(root); return result; } } class UnionFind { int[] P; this(int N) { P = new int[N]; P[] = -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(in Point a, in Point b) { return a.x * b.x + a.y * b.y; } real cross(in Point a, in Point b) { return a.x * b.y - a.y * b.x; } real norm(in 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; // a,b,cの順に反時計周り if (cross(b, c) < -EPS) return -1; // a,b,cの順に時計周り if (dot(b, c) < 0) return +2; // c--a--b 直線 if (norm(b) < norm(c)) return -2; // a--b--c 直線 return 0; // a--c--b 直線 } Point[] convexHull(in Point[] _ps) { auto ps = _ps.dup; assert(ps.size() >= 3); ps.sort!"a.x == b.x ? a.y < b.y : a.x < b.x"; int N = ps.size; int k = 0; auto ans = new Point[2 * N]; 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--; /* 返上の点も頂点としたい場合は上4行を * for (int i = 0; i < N; ans[k++] = ps[i++]) * while (k >= 2 && ccw(ans[k - 2], ans[k - 1], ps[i]) == -1) 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]) == -1) k--; * にする. */ return ans[0 .. k - 1]; } real diameter(in Point[] P) { // Pは凸多角形であり, かつその頂点は反時計回りでなければならない int N = P.size; int s = 0, t = 0; for (int k = 1; k < N; k++) { if (P[k].y < P[s].y) s = k; if (P[k].y > P[t].y) t = k; } real maxd = norm(P[s] - P[t]); int i = s, maxi = s; int j = t, maxj = t; int next(int k) { return (k + 1) % N; } do { if (cross(P[next(i)] - P[i], P[next(j)] - P[j]) >= 0) j = next(j); else i = next(i); if (norm(P[i] - P[j]) > maxd) { maxd = norm(P[i] - P[j]); maxi = i; maxj = j; } } while (i != s || j != t); return maxd; /* farthest pair is (maxi, maxj). */ } long dist_sq(in Point a, in Point b) { auto dx = a.x - b.x; auto dy = a.y - b.y; return dx * dx + dy * dy; } void main() { int N = readln.chomp.to!int; if (N == 0) { writefln("%.12f", 1.0); return; } auto P = new Point[N]; foreach (int i, ref p; P) { readf("%s %s\n", &p.x, &p.y); p.index = i; } auto t = new RangeTree(P.dup); auto uf = new UnionFind(N); foreach (i; 0 .. N) { long x = P[i].x, y = P[i].y; auto ns = t.query(x - 10, y - 10, x + 10, y + 10); foreach (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; Point[][int] gs; for (int i = 0; i < N; i++) { int k = uf.root(i); if (k in gs) { gs[k] ~= P[i]; } else { gs[k] = [P[i]]; } } foreach (vs; gs) { if (vs.size == 1) { // do nothing } else if (vs.size == 2) { ans = max(ans, norm(vs[0] - vs[1])); } else { auto hull = vs.convexHull; ans = max(ans, hull.diameter); } } writefln("%.12f", ans + 2.0); }