#include #include #include #include #include #include #include #include #include #include using namespace std; #define EPS 1e-6 class xy{ public: double x; double y; xy(){ } xy(double xx, double yy){ x = xx; y = yy; } xy(const xy &v){ x = v.x; y = v.y; } xy& operator=(const xy &v){ x = v.x; y = v.y; return *this; } xy operator+(const xy &v) const{ return xy(this->x+v.x, this->y+v.y); } xy operator-(const xy &v) const{ return xy(this->x-v.x, this->y-v.y); } void operator+=(const xy &v){ x+=v.x; y+=v.y; } void operator-=(const xy &v){ x-=v.x; y-=v.y; } /* something wrong this operator for sorting bool operator<(const xy &v){ if(x!=v.x) return x < v.x; return y < v.y; } bool operator>(const xy &v){ if(x!=v.x) return x > v.x; return y > v.y; } */ }; //for sorting bool comp_xy(const xy &a, const xy &b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y; } //u,v : vector O = (0,0) double cross(const xy &u, const xy &v){ return u.x*v.y - u.y*v.x; } //u,v : vector O = (0,0) double dot(const xy &u, const xy &v){ return u.x*v.x + u.y*v.y; } //distance between two points double dist_p_p(const xy &a, const xy &b){ return sqrt( fabs(dot(a-b, a-b)) ); } //distance between a point and a line segment double dist_p_ls(const xy &p, const xy &s1, const xy &s2){ xy vl = s2 - s1; xy vp = p - s1; return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) ); } //zero -> p1 int ccw(xy p1, xy p2, xy p3){ p2 -= p1; p3 -= p1; double c = cross(p2,p3); if( c > EPS /* c > 0 */) return +1; //counter-clockwise if( c < -EPS /* c < 0 */) return -1; //clock-wise if( dot(p2,p3) < -EPS) return +2; //on segment : p3-p1-p2 if( dot(p3,p3) < dot(p2,p2) +EPS ) return -2; //on segment : p1-p3-p2 return 0; } //segment p1-p2, p3-p4 bool inter_ss(xy p1, xy p2, xy p3, xy p4){ return ( (ccw(p1,p2, p3) * ccw(p1,p2, p4) <= 0) && (ccw(p3,p4, p1) * ccw(p3,p4, p2) <= 0 ) ) ; } //convex_hull vector convex_hull(vector &v){ sort( v.begin(), v.end(), comp_xy ); int k = 0; //nums of vertex vector tmp(v.size()*2); //conect i from k for(int i=0; i1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--; tmp[k] = v[i]; k++; } for(int i=v.size()-2, t=k; i>=0; i--){ while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--; tmp[k] = v[i]; k++; } tmp.resize(k-1); return tmp; } pair farthest_point_pair(vector &v /* v MUST BE CONVEX HULL*/){ int n = v.size(); int p = 0; //the point which has min y int q = 0; //the point which has max y for(int i=0; i v[i].y ) p = i; if( v[q].y < v[i].y ) q = i; } double max_dist = dist_p_p( v[p], v[q] ); int ret_a = p; int ret_b = q; int s = p; int t = q; while(1){ if( cross( v[(s+1)%n]-v[s], v[(t+1)%n] - v[t] ) < 0 ) s = (s+1)%n; else t = (t+1)%n; if( dist_p_p( v[s], v[t] ) > max_dist ){ ret_a = s; ret_b = t; max_dist = dist_p_p( v[s], v[t] ); } if( s==p && t==q ) break; } return make_pair(ret_a, ret_b); } class UnionFindTree{ typedef struct { int parent; int rank; }base_node; vector node; public: UnionFindTree(int n){ node.resize(n); for(int i=0; i node[y].rank){ node[y].parent = x; }else{ node[x].rank++; unite(x,y); } } }; bool check(xy &a, xy &b){ return dist_p_p(a,b) <= 10; } int main(){ int n; cin >> n; vector > events(n*2); vector Y(n); vector q(n); for(int i=0; i> x >> y; Y[i] = y; events.push_back( make_pair(x-10, i) ); events.push_back( make_pair(x+10, n+i) ); q[i] = xy(x,y); } sort(events.begin(), events.end()); UnionFindTree uft(n); set< pair > my_list; for(int i=0; isecond ]) ){ uft.unite(id, itr->second ); } } my_list.insert( make_pair( Y[id], id ) ); }else{ my_list.erase( make_pair( Y[id-n], id-n ) ); } } map > S; for(int i=0; i(0); S[par].push_back( q[i] ); } } double ans = 1.0; for(auto itr = S.begin(); itr != S.end(); itr++){ if(itr->second.size() == 1){ ans = max(ans, 2.0); continue; } vector hull = convex_hull( itr->second ); pair d = farthest_point_pair(hull); double tmp = dist_p_p( hull[d.first], hull[d.second] ) + 2.0; ans = max(ans, tmp); } printf("%.7f\n", ans); return 0; }