# include "bits/stdc++.h" using namespace std; using LL = long long; using ULL = unsigned long long; const double PI = acos(-1); templateconstexpr T INF() { return ::std::numeric_limits::max(); } templateconstexpr T HINF() { return INF() / 2; } template T_char TL(T_char cX) { return tolower(cX); }; template T_char TU(T_char cX) { return toupper(cX); }; const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }; int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; } int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; } int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; } LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); }; LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; }; # define ALL(qpqpq) (qpqpq).begin(),(qpqpq).end() # define UNIQUE(wpwpw) sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end()) # define LOWER(epepe) transform(ALL((epepe)),(epepe).begin(),TL) # define UPPER(rprpr) transform(ALL((rprpr)),(rprpr).begin(),TU) # define FOR(i,tptpt,ypypy) for(LL i=(tptpt);i<(ypypy);i++) # define REP(i,upupu) FOR(i,0,upupu) # define INIT std::ios::sync_with_stdio(false);std::cin.tie(0) //定義系 double EPS = 1e-10; //誤差を考慮して足し算を行う double add(double a, double b) { if (abs(a + b) < EPS*(abs(a) + abs(b)))return 0; return a + b; } //Point struct Point { double x, y; Point() {} Point(double x, double y) :x(x), y(y) { } Point operator + (Point p) { return Point(add(x, p.x), add(y, p.y)); } Point operator - (Point p) { return Point(add(x, -p.x), add(y, -p.y)); } Point operator * (double d) { return Point(x*d, y*d); } Point operator / (double d) { return Point(x / d, y / d); } //内積 double dot(Point p) { return add(x*p.x, y*p.y); } //外積 double det(Point p) { return add(x*p.y, -y*p.x); } //点の大小比較 bool operator <(const Point &p)const { if (fabs(add(x, -p.x)) < EPS)return y < p.y; return x < p.x; } bool operator ==(const Point &p)const { return fabs(x - p.x) < EPS&&fabs(y - p.y) < EPS; } }; //ベクトル。使い分けるといいかも typedef Point Vector; //ベクトルの大きさの2乗 double norm(Vector p) { return p.x*p.x + p.y*p.y; } //ベクトルの大きさ double abs(Vector p) { return sqrt(norm(p)); } //線分 struct Segment { Point p1, p2; }; //直線 typedef Segment Line; //中心c,半径rの円 struct Circle { Point c; double r; Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {} }; //多角形 typedef vector Polygon; //頂点集合 typedef vector Points; //計算・アルゴリズム系 //反時計回りCCW static const int COUNTER_CLOCKWISE = 1; static const int CLOCKWISE = -1; static const int ONLINE_BACK = 2; static const int ONLINE_FRONT = -2; static const int ON_SEGMENT = 0; int ccw(Point p0, Point p1, Point p2) { Vector a = p1 - p0; Vector b = p2 - p0; if (a.det(b) > EPS)return COUNTER_CLOCKWISE; if (a.det(b) < -EPS)return CLOCKWISE; if (a.dot(b) < -EPS)return ONLINE_BACK; if (norm(a) < norm(b))return ONLINE_FRONT; return ON_SEGMENT; } //線分p1p2と線分p3p4の交差判定 bool intersect(Point p1, Point p2, Point p3, Point p4) { return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0); } bool intersect(Segment s1, Segment s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2); } static const int ICC_SEPERATE = 4; static const int ICC_CIRCUMSCRIBE = 3; static const int ICC_INTERSECT = 2; static const int ICC_INSCRIBE = 1; static const int ICC_CONTAIN = 0; //円と円の交差判定 int intersect(Circle c1, Circle c2) { if (c1.rr) return ICC_SEPERATE; if (d + c2.r== c1.r) return ICC_INSCRIBE; if (d + c2.rgetCrossPoints(Circle c, Line l) { Vector pr = project(l, c.c); Vector e = (l.p2 - l.p1) / abs(l.p2 - l.p1); double base = sqrt(c.r*c.r - norm(pr - c.c)); return make_pair(pr + e*base, pr - e*base); } //円c1と円c2の交点 double arg(Vector p) { return atan2(p.y, p.x); } Vector polar(double a, double r) { return Point(cos(r)*a, sin(r)*a); } pairgetCrossPoints(Circle c1, Circle c2) { double d = abs(c1.c - c2.c); double a = acos((c1.r*c1.r + d*d - c2.r*c2.r) / (2 * c1.r*d)); double t = arg(c2.c - c1.c); return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)); } //点pを通る円cの接線 pair< Point, Point > tangent( Circle c1, Point p2) { pair d = getCrossPoints(c1, Circle(p2, sqrt(norm(c1.c - p2) - c1.r * c1.r))); return minmax(d.first, d.second); } //点の内包 0:in,1:on,2:out int contains(Polygon g, Point p) { int n = g.size(); bool x = false; for (int i = 0; i < n; i++) { Point a = g[i] - p, b = g[(i + 1) % n] - p; if (abs(a.det(b)) < EPS&&a.dot(b) < EPS) return 1; if (a.y > b.y)swap(a, b); if (a.y < EPS&&EPS < b.y&&EPS < a.det(b))x = !x; } return (x ? 2 : 0); } //凸包を求める(辺上も含める場合は!=CLOCKWISEを==COUNTER_CLOCKWISEに) Polygon convex_hull(Polygon s) { Polygon u, l; if (s.size() <= 2)return s; sort(s.begin(), s.end(), [](const Point &p1, const Point &p2) {return p1.y == p2.y ? p1.x= 2 && ccw(u[n - 2], u[n - 1], s[i]) == COUNTER_CLOCKWISE&&ccw(u[n - 2], u[n - 1], s[i]) != ONLINE_FRONT; n--){ u.pop_back(); } u.push_back(s[i]); } for (int i = s.size() - 3; i >= 0; i--){ for (int n = l.size(); n >= 2 && ccw(l[n - 2], l[n - 1], s[i]) != CLOCKWISE&&ccw(l[n - 2], l[n - 1], s[i]) != ONLINE_FRONT; n--){ l.pop_back(); } l.push_back(s[i]); } reverse(l.begin(), l.end()); for (int i = u.size() - 2; i >= 1; i--)l.push_back(u[i]); return l; } //y座標の昇順でマージするための比較関数 bool compare_y(Point a, Point b) { return a.y < b.y; } //最近点対 double closest_pair(Point *a, int n) { if (n <= 1)return INF(); sort(a, a + n); int m = n / 2; double x = a[m].x; double d = min({ closest_pair(a,m),closest_pair(a + m,n - m) });//p,qが違う区間にある inplace_merge(a, a + m, a + n, compare_y);//2つのソートされた列をマージ //p,qが同じ区間にある Points b;//直線から距離d未満の頂点を入れていく for (int i = 0; i < n; i++) { if (add(fabs(add(a[i].x, -x)), -d) >= 0.0)continue; //bに入っている頂点を、末尾からy座標の差がd以上になるまで見ていく for (int j = 0; j < (int)b.size(); j++) { Point dd; dd.x = add(a[i].x, -b[b.size() - j - 1].x); dd.y = add(a[i].y, -b[b.size() - j - 1].y); if (add(dd.y, -d) >= 0.0)break; d = min(d, abs(dd)); } b.emplace_back(a[i]); } return d; } //多角形の面積 double area(Polygon p) { int n = p.size(); double sum = 0.0; for (int i = 0; i < n; i++) { sum = add(sum,0.5*p[i].det(p[(i + 1) % n])); } return sum < 0.0 ? -sum : sum; } //凸性判定 bool is_convex(Polygon p) { for (int i = 0; i < (int)p.size(); i++) { if (ccw(p[(i - 1 + p.size()) % p.size()], p[i], p[(i + 1) % p.size()]) == -1)return false; } return true; } //切断 Polygon convex_cut(Polygon p, Line l) { Polygon ret; for (int i = 0; i < (int)p.size(); i++) { Point cur = p[i], nxt = p[(i + 1) % p.size()]; if (ccw(l.p1, l.p2, cur) != -1)ret.emplace_back(cur); if (ccw(l.p1, l.p2, cur)*ccw(l.p1, l.p2, nxt) < 0) { Segment seg; seg.p1 = cur; seg.p2 = nxt; ret.emplace_back(getCrossPoint(seg, l)); } } return ret; } //端点の種類 # define BOTTOM 0 # define LEFT 1 # define RIGHT 2 # define TOP 3 class EndPoint { public: Point p; int seg, st;//入力線分のID,端点の種類 EndPoint() {} EndPoint(Point p, int seg, int st) :p(p), seg(seg), st(st) {} bool operator <(const EndPoint &ep)const { //y座標が小さい順に整列 if (p.y == ep.p.y) { return st < ep.st;//yが同一の場合は、下端点、左端点、右端点、上端点の順に調べる } else { return p.y < ep.p.y; } } }; EndPoint EP[202020];//端点のリスト //線分交差問題(マンハッタン幾何) int ManhattanIntersection(vector s) { int n = s.size(); for (int i = 0, k = 0; i < n; i++) { //端点p1,p2が左下を基準に並ぶように調整 if (s[i].p1.y == s[i].p2.y) { if(s[i].p1.x>s[i].p2.x)swap(s[i].p1, s[i].p2); } else if (s[i].p1.y > s[i].p2.y)swap(s[i].p1, s[i].p2); if (s[i].p1.y == s[i].p2.y) {//水平線分を端点リストに追加 EP[k++] = EndPoint(s[i].p1, i, LEFT); EP[k++] = EndPoint(s[i].p2, i, RIGHT); } else {//垂直線分を端点リストに追加 EP[k++] = EndPoint(s[i].p1, i, BOTTOM); EP[k++] = EndPoint(s[i].p2, i, TOP); } } sort(EP, EP + 2 * n);//端点のy座標に関して昇順に整列 set bt;//二分探索木 bt.insert(1010101010); int cnt = 0; for (int i = 0; i < 2 * n; i++) { if (EP[i].st == TOP) { bt.erase(EP[i].p.x);//上端点を削除 } else if (EP[i].st == BOTTOM) { bt.insert(EP[i].p.x); } else if (EP[i].st == LEFT) { set::iterator b = bt.lower_bound(s[EP[i].seg].p1.x); set::iterator e = bt.upper_bound(s[EP[i].seg].p2.x); cnt += distance(b, e);//bとeの距離(点の数)を加算 } } return cnt; } struct UnionFind { UnionFind(size_t size){ for(int i = 0;i < (int)size;i++){ par.emplace_back(i); rnk.emplace_back(0); } } vector par, rnk; int find(int x){ if(par[x] == x)return x; else return par[x] = find(par[x]); } void unite(int x, int y){ x = find(x); y = find(y); if(x == y)return; if(rnk[x] < rnk[y]){ par[x] = y; }else{ par[y] = x; if(rnk[x] == rnk[y])rnk[x]++; } } bool same(int x,int y){ return find(x) == find(y); } }; int n; Points p; vector bg[2525][2525]; Points ufgroup[121212]; const int geta = 1010; int main(){ INIT; cin >> n; p.resize(n); REP(i, n){ cin >> p[i].x >> p[i].y; bg[(int)p[i].y/10 + geta][(int)p[i].x/10 + geta].emplace_back(i); } if(n == 0){ cout << fixed << setprecision(10) << 1.0 << endl; return 0; } UnionFind uf(n); REP(i, n){ int by = (int)p[i].y/10 + geta, bx = (int)p[i].x/10 + geta; REP(u, (int)bg[by][bx].size()){ if(bg[by][bx][u] == i)continue; if(getDistance(p[i], p[bg[by][bx][u]]) <= 10.0){ uf.unite(i, bg[by][bx][u]); } } REP(k, 8){ int ny = by + vy[k], nx = bx + vx[k]; REP(u, (int)bg[ny][nx].size()){ if(getDistance(p[i], p[bg[ny][nx][u]]) <= 10.0){ uf.unite(i, bg[ny][nx][u]); } } } } REP(i, n){ ufgroup[uf.find(i)].emplace_back(p[i]); } double ans = 0.0; REP(i, n){ if(ufgroup[i].empty())continue; Points cp = convex_hull(ufgroup[i]); REP(u, (int)cp.size()){ REP(v, (int)cp.size()){ ans = max(ans, getDistance(cp[u], cp[v])); } } } cout << fixed << setprecision(10) << ans + 2.0 << endl; }