/* -*- coding: utf-8 -*- * * 96.cc: No.96 圏外です。 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 120000; const int CX = 10000; const int CY = 10000; const int BXN = (CX * 2) / 10; const int BYN = (CY * 2) / 10; typedef long long ll; const int INF = 1 << 30; const ll LINF = 1LL << 60; /* typedef */ typedef vector vi; typedef queue qi; typedef pair pii; template struct Pt { T x, y; Pt() {} Pt(T _x, T _y) : x(_x), y(_y) {} Pt(const Pt& pt) : x(pt.x), y(pt.y) {} bool operator==(const Pt pt) const { return x == pt.x && y == pt.y; } bool operator!=(const Pt pt) const { return x != pt.x || y != pt.y; } Pt operator+(const Pt pt) const { return Pt(x + pt.x, y + pt.y); } Pt operator-() const { return Pt(-x, -y); } Pt operator-(const Pt pt) const { return Pt(x - pt.x, y - pt.y); } Pt operator*(T t) const { return Pt(x * t, y * t); } Pt operator/(T t) const { return Pt(x / t, y / t); } T dot(Pt v) const { return x * v.x + y * v.y; } T cross(Pt v) const { return x * v.y - y * v.x; } Pt mid(const Pt pt) { return Pt((x + pt.x) / 2, (y + pt.y) / 2); } T d2() { return x * x + y * y; } double d() { return sqrt(d2()); } Pt rot(double th) { double c = cos(th), s = sin(th); return Pt(c * x - s * y, s * x + c * y); } Pt rot90() { return Pt(-y, x); } bool operator<(const Pt& pt) const { return x < pt.x || (x == pt.x && y < pt.y); } void print(string format) { printf(("(" + format + ", " + format + ")\n").c_str(), x, y); } void print() { print("%.6lf"); } }; typedef Pt pt; typedef vector vpt; struct UFT { int links[MAX_N], ranks[MAX_N], sizes[MAX_N]; void clear(int n) { for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1; } UFT() {} UFT(int n) { clear(n); } int root(int i) { int i0 = i; while (links[i0] != i0) i0 = links[i0]; return (links[i] = i0); } int rank(int i) { return ranks[root(i)]; } int size(int i) { return sizes[root(i)]; } bool same(int i, int j) { return root(i) == root(j); } int merge(int i0, int i1) { int r0 = root(i0), r1 = root(i1), mr; if (r0 == r1) return r0; if (ranks[r0] == ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; ranks[r0]++; mr = r0; } else if (ranks[r0] > ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; mr = r0; } else { links[r0] = r1; sizes[r1] += sizes[r0]; mr = r1; } return mr; } }; /* global variables */ pt ps[MAX_N]; vi bps[BYN + 1][BXN + 1], cps[MAX_N]; UFT uft; bool used[MAX_N]; /* subroutines */ void convex_hull(const vi& cp, vpt& chs) { int n = cp.size(); vpt lhs, uhs; lhs.push_back(ps[cp[0]]); lhs.push_back(ps[cp[1]]); for (int i = 2; i < n; i++) { int ln = lhs.size(); pt &lh0 = lhs[ln - 2], &lh1 = lhs[ln - 1]; if ((lh1 - lh0).cross(ps[cp[i]] - lh1) < 0) lhs.pop_back(); lhs.push_back(ps[i]); } uhs.push_back(ps[cp[n - 1]]); uhs.push_back(ps[cp[n - 2]]); for (int i = n - 3; i >= 0; i--) { int un = uhs.size(); pt &uh0 = uhs[un - 2], &uh1 = uhs[un - 1]; if ((uh1 - uh0).cross(ps[cp[i]] - uh1) < 0) uhs.pop_back(); uhs.push_back(ps[i]); } lhs.pop_back(); uhs.pop_back(); chs.clear(); chs.reserve(lhs.size() + uhs.size()); chs.assign(lhs.begin(), lhs.end()); chs.insert(chs.end(), uhs.begin(), uhs.end()); } /* main */ int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> ps[i].x >> ps[i].y; if (n == 0) { printf("%.9lf\n", 1.0); return 0; } for (int i = 0; i < n; i++) { int bx = (ps[i].x + CX) / 10, by = (ps[i].y + CY) / 10; bps[by][bx].push_back(i); } uft.clear(n); for (int by0 = 0; by0 <= BYN; by0++) for (int bx0 = 0; bx0 <= BXN; bx0++) { vi &bp0 = bps[by0][bx0]; for (vi::iterator uit = bp0.begin(); uit != bp0.end(); uit++) { int &u = *uit; for (int by = by0 - 1; by <= by0 + 1; by++) if (by >= 0 && by <= BYN) for (int bx = bx0 - 1; bx <= bx0 + 1; bx++) if (bx >= 0 && bx <= BXN) { vi &bp1 = bps[by][bx]; for (vi::iterator vit = bp1.begin(); vit != bp1.end(); vit++) { int &v = *vit; if (uft.root(u) != uft.root(v) && (ps[v] - ps[u]).d2() <= 10 * 10) uft.merge(u, v); } } } } for (int i = 0; i < n; i++) cps[uft.root(i)].push_back(i); int maxd2 = 0; for (int i = 0; i < n; i++) { vi &cpi = cps[i]; if (cpi.size() > 1) { vpt chs; convex_hull(cpi, chs); int hn = chs.size(); for (int j = 0; j < hn; j++) for (int k = j + 1; k < hn; k++) { int d2 = (chs[k] - chs[j]).d2(); if (maxd2 < d2) maxd2 = d2; } } } printf("%.9lf\n", sqrt((double)maxd2) + 2.0); return 0; }