// kroton 氏の回答を参考に..... #include using namespace std; typedef long long int ll; typedef pair pii; typedef vector vi; typedef vector > vii; #define rrep(i, m, n) for(int (i)=(m); (i)<(n); (i)++) #define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++) #define rep(i, n) for(int (i)=0; (i)<(n); (i)++) #define rev(i, n) for(int (i)=(n)-1; (i)>=0; (i)--) #define vrep(i, c) for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++) #define ALL(v) (v).begin(), (v).end() #define mp make_pair #define pb push_back template inline void minup(T1& m, T2 x){ if(m>x) m=static_cast(x); } template inline void maxup(T1& m, T2 x){ if(m(x); } #define INF 1000000000 #define MOD 1000000007 #define EPS 1E-12 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 dot(const P& a, const P& b){ return real(conj(a)*b); } // 内積 double det(const P& a, const P& b){ return imag(conj(a)*b); } // 外積 typedef vector

G; int ccw(P a, P b, P c) { b -= a; c -= a; if (det(b, c) > 0) return +1; // counter clockwise if (det(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; } vector

AndrewMonotoneChain(vector

ps) { int n = ps.size(), k = 0; sort(ps.begin(), ps.end()); vector

ch(2*n); for(int i=0; i= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; for(int i=n-2, t=k+1; i>= 0; ch[k++]=ps[i--]) // upper-hull while(k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; ch.resize(k-1); return ch; } double Caliper(const vector

& v) { int n = v.size(); int si = 0; int sj = 0; rep(t, n){ if(v[t].imag() < v[si].imag()) si = t; if(v[t].imag() > v[sj].imag()) sj = t; } double res = 0; int i = si; int j = sj; do{ maxup(res, abs(v[i]-v[j])); P di = v[(i+1)%n] - v[i]; P dj = v[(j+1)%n] - v[j]; if(det(di, dj) >= 0) j = (j+1)%n; else i = (i+1)%n; }while(!(i == si && j == sj)); return res; } const int MAX_N = 120000; const double MAX_XY = 10000.0; const int B = 50; int n; double x, y; P z[MAX_N]; double res; bool used[MAX_N]; vi bucket[2 * MAX_N / 10 / B][2 * MAX_N / 10 / B]; bool check(P z, P w){ return (z-w).real()*(z-w).real()+(z-w).imag()*(z-w).imag() <= 100.0; } bool check(int x, int y){ return 0<=x && 0<=y; } int main() { cin >> n; rep(i, n){ cin >> x >> y; z[i] = P(x + MAX_XY, y + MAX_XY); } if(n == 0){ puts("1"); return 0; } rep(i, n){ bucket[(int)(z[i].real()/B)][(int)(z[i].imag()/B)].pb(i); } vi g[MAX_N]; rep(i, n) erep(dx, -1, 1) erep(dy, -1, 1){ int nx = z[i].real() / B + dx; int ny = z[i].imag() / B + dy; if(!check(nx, ny)) continue; // g[i].pb(i); vrep(v, bucket[nx][ny]){ if(i != *v && check(z[i], z[*v])) g[i].pb(*v); } } rep(i, n) if(!used[i]){ G ConvexHull; ConvexHull.pb(z[i]); queue que; que.push(i); used[i] = true; while(!que.empty()){ int top = que.front(); que.pop(); vrep(v, g[top]) if(!used[*v]){ used[*v] = true; que.push(*v); ConvexHull.pb(z[*v]); } } if(ConvexHull.size() == 2) maxup(res, abs(ConvexHull[0] - ConvexHull[1])); if(ConvexHull.size() > 2){ ConvexHull = AndrewMonotoneChain(ConvexHull); maxup(res, Caliper(ConvexHull)); } } printf("%.10f\n", res + 2.0); return 0; }