#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int lli; typedef unsigned int uint; typedef unsigned char uchar; typedef unsigned long long ull; #define REP(i,x) for(int i=0;i<(int)(x);i++) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define RREP(i,x) for(int i=(x);i>=0;i--) #define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++) const double EPS=1e-5; const double INF=1e10; const double PI = M_PI; // 平面上の点 struct Point{ Point(double x, double y):x(x) ,y(y){} Point(){} double x,y; }; Point operator+(const Point &a, const Point &b){ return Point(a.x + b.x, a.y + b.y); } Point operator-(const Point &a, const Point &b){ return Point(a.x - b.x, a.y - b.y); } Point operator*(const Point &a, const double b){ return Point(a.x * b, a.y * b); } // 必要時定義(複素数の積) Point operator*(const Point &a,const Point &b){ return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x); } // 必要時定義 (基本的に * 1.0 / (ほげほげ)で済ます Point operator/(const Point &a, const double b){ return Point(a.x / b, a.y / b); } // 外積 a × b double cross(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x; } // 内積 a ・ b double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y; } // 比較 (必要時のみ定義) bool operator<(const Point &a, const Point &b){ return make_pair(a.x, a.y) < make_pair(b.x, b.y); } // 角度(必要時のみ定義) double atan(const Point &a){ return atan2(a.y, a.x); } // |a|^2 double norm(const Point &a){ return dot(a, a); } // |a| double abs(const Point &a){ return sqrt(norm(a)); } // 点の90度回転(必要時定義) Point rotate90(const Point &a){ return Point(-a.y, a.x); } // 点の回転(必要時定義) ラジアン注意 Point rotate(const Point &a, double angle){ return Point(cos(angle) * a.x - sin(angle) * a.y, sin(angle) * a.x + cos(angle) * a.y); } // 直線・線分 struct Line:vector{ Line(Point a = Point(0,0), Point b = Point(0,0)){ this->push_back(a); this->push_back(b); } }; // 円 struct Circle: Point{ double r; Circle(Point p = Point(0,0), double r=0):Point(p),r(r){} }; // 多角形 typedef vector Polygon; // 前後の頂点情報(必要時のみ) Point next(const Polygon &a, int x){ return a[(x + 1) % a.size()]; } Point prev(const Polygon &a, int x){ return a[(x - 1 + a.size()) % a.size()]; } ostream& operator<<(ostream &os, const Point &a){ return os<<"("<>(istream &is, Point &a){ return is>>a.x>>a.y; } int ccw(Point a, Point b, Point c){ b = b - a; c = c - a; if (cross(b, c) > EPS) return +1; // 反時計周り if (cross(b, c) < -EPS) return -1;// 時計周り 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が一直線上 } // 直線交差判定 // 同一直線の場合は交差していると判定する。 bool is_intersect_LL(const Line &l, const Line &m){ return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // 傾きが異なる abs(cross(l[1] - l[0], m[1] - l[0])) < EPS; // 同じ直線である } // 直線と線分の交差判定 // 同一直線上にある場合も交差と判定 bool is_intersect_LS(const Line &l, const Line &s){ return cross(l[1] - l[0], s[0] - l[0]) * cross(l[1] - l[0], s[1] - l[0]) < EPS; } // 直線が線分を含むかの判定 bool is_intersect_LP(const Line &l, const Point &p){ return abs(ccw(l[0], l[1], p))!=1; } // 線分交差判定 bool is_intersect_SS(const Line &s, const Line &t){ return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0; } // 線分が直線を含むかどうか bool is_intersect_SP(const Line &l, const Point &p){ return ccw(l[0], l[1], p) == 0; } // 円が点を含むかどうか(境界含む EPSに注意) bool is_intersect_CP(const Circle &c, const Point &p){ return abs(c-p)<=c.r+EPS; } // 2円が共有点を持つかどうか (EPSに注意) bool is_intersect_CC(const Circle &c,const Circle &d){ return abs(c-d)<=c.r+d.r && abs(c-d)>= abs(c.r-d.r); } // 写像 Point projection(const Line &l, const Point &p){ double t = dot(p - l[0], l[1] - l[0]) / norm(l[0] - l[1]); return l[0] + (l[1] - l[0]) * t; } // 反射 Point reflection(const Line &l, const Point &p){ return p + (projection(l, p) - p) * 2; } // 直線と点の距離 double distance_LP(const Line &l, const Point &p){ return abs(p - projection(l, p)); } // 直線と直線の距離 double distance_LL(const Line &l, const Line &m){ return is_intersect_LL(l, m) ? 0 : distance_LP(l, m[0]); } // 直線と線分の距離 double distance_LS(const Line &l, const Line &s){ if(is_intersect_LS(l, s)) return 0; return min(distance_LP(l, s[0]),distance_LP(l, s[1])); } // 線分と点の距離 double distance_SP(const Line &s, const Point &p){ const Point r = projection(s, p); if(is_intersect_SP(s, r))return abs(r - p); return min(abs(s[0] - p), abs(s[1] - p)); } // 線分同士の距離 double distance_SS(const Line &s, const Line &t){ if(is_intersect_SS(s, t)) return 0; return min(min(distance_SP(s, t[0]), distance_SP(s, t[1])), min(distance_SP(t, s[0]), distance_SP(t, s[1]))); } // 直線の交点 Point crosspoint_LL(const Line &l,const Line &m){ double d = cross(m[1] - m[0], l[1] - l[0]); if(abs(d) < EPS) throw "線分が平行です"; // 線分が平行。場合によってはl[0]を返すようにする return l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) * (1.0 / d); } // 2円の交点 vector crosspoint_CC(const Circle &c1,const Circle &c2){ vector res; if(abs(c1-c2)(); // 交点が絶対にない double d=abs(c1-c2); double rc=(d*d+c1.r*c1.r-c2.r*c2.r)/(2*d); double rs=sqrt(c1.r*c1.r-rc*rc); Point diff = (c2 - c1)/d; res.push_back(Point(c1 + diff * Point(rc,rs))); res.push_back(Point(c1 + diff * Point(rc,-rs))); return res; } // 円と線分の直線 vector crosspoint_CL(const Circle &a,const Line &b){ vector res; double dist=distance_LP(b,a); if(dist<=a.r){ Point s=projection(b,a); dist=sqrt(a.r*a.r-dist*dist); Point t=(b[1]-b[0])/abs(b[1]-b[0]); res.push_back(s+t*dist); res.push_back(s-t*dist); } return res; } // 点pから引いた円の接点 vector tangentCP(const Circle &c, const Point &p){ double x = norm(p - c); double d = x - c.r * c.r; if(d < -EPS) return vector(); d = max(d, 0.0); Point q1 = (p - c) * (c.r * c.r / x); Point q2 = rotate90((p - c) * (-c.r * sqrt(d) / x)); vector ret; ret.push_back(c + q1 - q2); ret.push_back(c + q1 + q2); return ret; } // 2円の共通接線を求める vector tangentCC(const Circle &a, const Circle &b){ vector list; // 外接線の計算 if(abs(a.r - b.r) < EPS){ // 2円の半径が同じ Point dir = b - a; dir = rotate90(dir * (a.r / abs(dir))); list.push_back(Line(a + dir, b + dir)); list.push_back(Line(a - dir, b - dir)); } else { Point p = (a * (-b.r)) + (b * a.r); p = p * (1 / (a.r - b.r)); vector ps = tangentCP(a, p); vector qs = tangentCP(b, p); REP(i, min(ps.size(),qs.size())){ list.push_back(Line(ps[i],qs[i])); } } // 内接線の計算 Point p = (a * b.r) + (b * a.r); p = p * (1 / (a.r + b.r)); vector ps = tangentCP(a, p); vector qs = tangentCP(b, p); REP(i, min(ps.size(),qs.size())){ list.push_back(Line(ps[i],qs[i])); } return list; } double area(const Polygon &a){ double ret = 0.0; REP(i, a.size()){ ret += cross(a[i], next(a, i)); } return abs(ret) * .5; } // 多角形の重心を求める Point center_of_gravity(const Polygon &P){ Point p; REP(i, P.size())p=p+P[i]; return p*(1.0/P.size()); } pair smallest_enclosing_circle(const vector &pts){ Point p(0,0); REP(i,pts.size())p = p + pts[i]; p = p * (1. / pts.size()); // 初期の点を重心にする double d = 0.5; // ステップ数を増やすと精度が良くなる for(int k = 1; k <= 30; k++){ for(int i = 0; i < 10 ; i++){ int s = 0; REP(i, pts.size()){ if(abs(pts[i] - p) > abs(pts[s] - p)){ s = i; } } p = p + (pts[s] - p) * d; } d *= 0.5; } double max_dist = 0; REP(i, pts.size()){ if(abs(pts[i] - p) > max_dist){ max_dist = abs(pts[i] - p); } } return make_pair(p, max_dist); } vector convex_hull(vector ps) { int n=ps.size(), k=0; sort(ps.begin(), ps.end()); vector ch(2*n); for (int i=0; i < n; ch[k++]=ps[i++]) // lower-hull while (k >= 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; } /* 扇型 */ struct Sector : public Circle{ double angle; // 開始角度(ラジアン) double size; // 角度の大きさ(ラジアン) Sector(Point p=Point(0,0),double r=0,double a=0,double l=0): Circle(p,r), angle(a), size(l) {} }; // 点が扇型に含まれるかどうか bool is_intersect_SecP(const Sector &sec,const Point &p){ if(!is_intersect_CP(sec, p))return false; if(abs(p-sec) crosspoint_LQ(double a,double b,double c,double A,double B,double C,double D,double E,double F){ if(b==0){ vector ret=crosspoint_LQ(b,a,c,C,B,A,E,D,F); REP(i,ret.size()){ ret[i]=Point(ret[i].y,ret[i].x); } return ret; } double P=A*b*b-B*b*a+C*a*a; double Q=-B*b*c+2*C*a*c+D*b*b-E*a*b; double R=C*c*c-E*b*c+F*b*b; if(P==0){ double x=-R/Q; vector ret; ret.push_back(Point(x,(-a*x-c)/b)); return ret; }else{ double d=Q*Q-4*P*R; vector ret; if(d==0){ double x=-Q/(2*P); ret.push_back(Point(x,(-a*x-c)/b)); }else if(d>0){ double x=(-Q-sqrt(d))/(2*P); ret.push_back(Point(x,(-a*x-c)/b)); x=(-Q+sqrt(d))/(2*P); ret.push_back(Point(x,(-a*x-c)/b)); } return ret; } } struct UnionFind{ vector par;vector rank; UnionFind(int n){ par=vector(n);rank=vector(n); for(int i=0;i X, Y; const int MAX_X = 20001; const int SPLIT_X = 200; int MAP[SPLIT_X][MAX_X]; vector dx, dy; void init() { for(int x = -10; x <= 10; x++) { for(int y = -10; y <= 10; y++) { if((x | y ) == 0) continue; if(x * x + y * y <= 100) { dx.push_back(x); dy.push_back(y); } } } memset(MAP, -1, sizeof(MAP)); } int main() { init(); cin >> N; X = vector(N); Y = vector(N); vector> pts[MAX_X]; for(int i = 0; i < N; i++) { cin >> X[i] >> Y[i]; X[i] += 10000; Y[i] += 10000; pts[X[i]].emplace_back(Y[i], i); } for(int x = 0; x <= 10; x++) { for(int i = 0; i < pts[x].size(); i++) { MAP[x][pts[x][i].first] = pts[x][i].second; } } UnionFind uf(N); for(int x = 0; x < MAX_X; x++) { for(int i = 0; i < pts[x].size(); i++) { int y = pts[x][i].first, pno = pts[x][i].second; for(int k = 0; k < dx.size(); k++) { int nx = x + dx[k], ny = y + dy[k]; if(nx < 0 || ny < 0 || nx >= MAX_X || ny >= MAX_X) continue; if(MAP[nx % SPLIT_X][ny] != -1) { int to = MAP[nx % SPLIT_X][ny]; uf.unite(pno, to); } } } // 更新 if(x - 10 >= 0) { for(int i = 0; i < pts[x - 10].size(); i++) { int y = pts[x - 10][i].first; MAP[(x - 10) % SPLIT_X][y] = -1; } } if(x + 11 < MAX_X) { for(int i = 0; i < pts[x + 11].size(); i++) { int y = pts[x + 11][i].first; MAP[(x + 11) % SPLIT_X][y] = pts[x + 11][i].second; } } } // UnionFind木を使っていろいろやる vector > pt_grp(N); for(int i = 0; i < N; i++) { pt_grp[uf.find(i)].push_back(i); } double ans = 2; if(N == 0) ans = 1; for(int i = 0; i < N; i++) { if(pt_grp[i].size() <= 1) continue; vector points; for(int k: pt_grp[i]) { points.push_back(Point(X[k], Y[k])); } points = convex_hull(points); for(int i = 0; i < points.size(); i++) { for(int j = 0; j < i; j++) { ans = max(ans, 2 + abs(points[i] - points[j])); } } } cout << setprecision(20) << ans << endl; }