#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); typedef long long ll; typedef unsigned long long ull; #define ALL(c) (c).begin(), (c).end() #define CLEAR(v) memset(v,0,sizeof(v)) #define MP(a,b) make_pair((a),(b)) #define REP(i,n) for(int i=0;i<(int)n;++i) #define ABS(a) ((a)>0?(a):-(a)) template T MIN(const T& a, const T& b) { return a < b ? a : b; } template T MAX(const T& a, const T& b) { return a > b ? a : b; } template void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; } template void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; } typedef complex P; const double INF = 1e12; typedef complex P; namespace std { bool operator < (const P& a, const P& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); } } double cross(const P& a, const P& b) { return imag(conj(a)*b); } double dot(const P& a, const P& b) { return real(conj(a)*b); } struct L : public vector

{ L(const P &a, const P &b) { push_back(a); push_back(b); } }; typedef vector

G; struct C { P p; double r; C(const P &p, double r) : p(p), r(r) { } }; int ccw(P a, P b, P c) { b -= a; c -= a; if (cross(b, c) > 0) return +1; // counter clockwise if (cross(b, c) < 0) return -1; // clockwise if (dot(b, c) < 0) return +2; // c--a--b on line if (norm(b) < norm(c)) return -2; // a--b--c on line return 0; } bool cmp_x(const P& p, const P& q) { if (p.real() != q.real()) return p.real() < q.real(); return p.imag() < q.imag(); } vector

convex_hull(P* ps, int n) { sort(ps, ps + n, cmp_x); int k = 0; vector

qs(n * 2); REP(i, n) { while (k > 1 && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) --k; qs[k++] = ps[i]; } for (int i = n - 2, t = k; i >= 0; --i) { while (k > t && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) --k; qs[k++] = ps[i]; } qs.resize(k - 1); return qs; } struct UnionFind { vector data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main() { std::ios::sync_with_stdio(false); int N; cin >> N; vector X; vector Y; vector

pos; REP(n, N) { int x, y; cin >> x >> y; pos.push_back(P(x, y)); X.push_back(x); Y.push_back(y); } static vector cells[2048][2048]; REP(n, N) { int x = X[n]; int y = Y[n]; int cellX = (x + 10000) / 10; int cellY = (y + 10000) / 10; REP(dx, 3) REP(dy, 3) { cells[cellX + dx][cellY + dy].push_back(n); } } UnionFind uf(N); REP(cellX, 2048) { REP(cellY, 2048) { const auto& ps = cells[cellX][cellY]; REP(i, ps.size()) { REP(j, i) { if ((X[ps[i]] - X[ps[j]]) * (X[ps[i]] - X[ps[j]]) + (Y[ps[i]] - Y[ps[j]]) * (Y[ps[i]] - Y[ps[j]]) <= 100) { uf.unionSet(ps[i], ps[j]); } } } } } map > points; REP(i, N) { points[uf.root(i)].push_back(pos[i]); } double answer = 1.0; //int counter = 0; //cerr << "points.size(): " << points.size() << endl; for (auto& connected : points) { //if (counter == 15281) { // int temp = 0; //} //if (15200 <= counter && counter <= 15300) { // cerr << counter << endl; //} //++counter; int n = connected.second.size(); if (n == 1) { MAX_UPDATE(answer, 2.0); continue; } if (n == 2) { MAX_UPDATE(answer, abs(connected.second[0] - connected.second[1]) + 2.0); continue; } vector

qs = convex_hull(&connected.second[0], connected.second.size()); n = qs.size(); if (n < 10) { REP(i, n) REP(j, i) { MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0); } continue; } int i = 0; int j = 0; for (int k = 0; k < n; ++k) { if (!cmp_x(qs[i], qs[k])) i = k; if (cmp_x(qs[j], qs[k])) j = k; } int si = i, sj = j; while (i != sj || j != si) { MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0); if (cross(qs[(i + 1) % n] - qs[i], qs[(j + 1) % n] - qs[j]) < 0) { i = (i + 1) % n; } else { j = (j + 1) % n; } } } printf("%.20f\n", answer); }