#include #include #include using namespace atcoder; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000000000 const long double eps = 1e-10; template struct vector_2d{ T x,y,rad,dir; vector_2d(T a=0.0,T b=0.0){ x = a; y = b; fix_rd(); } void update_x(T a,T b){ x = a*x + b; fix_rd(); } void update_x(T a){ update_x(0.0,a); } void update_y(T a,T b){ y = a*y + b; fix_rd(); } void update_y(T a){ update_y(0.0,a); } void update_rad(T a,T b){ rad = a*rad + b; fix_xy(); } void update_rad(T a){ update_rad(0.0,a); } void update_dir(T a,T b){ dir = a*dir + b; fix_xy(); } void update_dir(T a){ update_dir(0.0,a); } void fix_xy(){ x = rad * cos(dir); y = rad * sin(dir); fix_rd(); } void fix_rd(){ rad = hypot(x,y); if(rad==0.0)dir=0.0; else dir = atan2(y,x); fix_zero(); } void fix_zero(){ if(abs(x) V){ return hypot(x-V.x,y-V.y); } T size(){ return get_dis(vector_2d()); } T angle_difference(vector_2d V){ long double ret = dir - V.dir; if(ret<-acos(-1.0))ret = acos(-1.0)*2.0+ret; if(ret>acos(-1.0))ret=-acos(-1.0)*2.0+ret; return ret; } //中点 vector_2d get_midpoint(vector_2d V){ V.update_x(0.5,x/2.0); V.update_y(0.5,y/2.0); return V; } T get_inner_product(vector_2d V){ return x*V.x+y*V.y; } T get_cross_product(vector_2d V){ return x*V.y-y*V.x; } vector_2d &operator+=(const vector_2d &another){ update_x(1,another.x); update_y(1,another.y); return (*this); } vector_2d &operator-=(const vector_2d &another){ update_x(1,-another.x); update_y(1,-another.y); return (*this); } vector_2d operator+(const vector_2d &another)const{ return (vector_2d(*this)+=another); } vector_2d operator-(const vector_2d &another)const{ return (vector_2d(*this)-=another); } void show(){ cout< struct line{ vector_2d a,t; line(vector_2d V1,vector_2d V2){ a=V1; t=V2-V1; } T get_signed_dis(vector_2d V){ vector_2d PA = a-V; return PA.get_cross_product(t)/t.size(); } T get_dis(vector_2d V){ return abs(get_signed_dis(V)); } vector_2d get_projection(vector_2d P){ T r = t.get_inner_product(P-a)/t.size(); vector_2d temp = t; temp.update_rad(0.0,r); return a+temp; } vector_2d get_cross_point(line L){ vector_2d ret(1e20,1e20); if(abs(t.get_cross_product(L.t)) temp = t; temp.x *= d0/(d1-d0); temp.y *= d0/(d1-d0); ret = a - temp; return ret; } }; template struct segment{ vector_2d V1,V2; segment(vector_2d a=vector_2d(),vector_2d b=vector_2d()){ V1=a; V2=b; } T get_dis(vector_2d P){ T ret = 1e20; line L(V1,V2); vector_2d Q = L.get_projection(P); if(Q.x+eps>min(V1.x,V2.x)&&Q.y+eps>min(V1.y,V2.y) &&Q.x l){ if(get_cross_point(l).x<1e20)return 0.0; return min({get_dis(l.V1),get_dis(l.V2),l.get_dis(V1),l.get_dis(V2)}); } vector_2d get_cross_point(segment l){ line L1(V1,V2),L2(l.V1,l.V2); vector_2d P = L1.get_cross_point(L2); if(get_dis(P) (1e20,1e20); } }; template struct triangle{ vector_2d V[3]; triangle(vector_2d V1,vector_2d V2,vector_2d V3){ V[0] = V1; V[1] = V2; V[2] = V3; } vector_2d get_circumcenter(){ line L1(V[0],V[1]); vector_2d M1 = V[0].get_midpoint(V[1]); L1 = line(M1,L1.b,L1.a); line L2(V[1],V[2]); vector_2d M2 = V[1].get_midpoint(V[2]); L2 = line(M2,L2.b,L2.a); return L1.get_cross_point(L2); } T get_signed_area(){ return ((V[1].x-V[0].x)*(V[2].y-V[0].y) - (V[2].x-V[0].x)*(V[1].y-V[0].y))/2.0; } T get_area(){ return abs(get_signed_area()); } bool is_inside(vector_2d P){ T S = triangle(V[0],V[1],P).get_area() + triangle(V[1],V[2],P).get_area() + triangle(V[2],V[0],P).get_area(); return abs(S - get_area()) X = V[1]-V[0],Y = V[2]-V[1]; return X.x*Y.y-X.y*Y.x < 0.0; } }; template struct polygon{ vector> V; polygon(vector> v){ V = v; } bool is_convex(){ bool f = false; for(int i=0;i tri(V[i],V[(i+1)%V.size()],V[(i+2)%V.size()]); if(i==0)f = tri.is_clockwise(); else{ if(tri.is_clockwise()!=f)return false; } } return true; } T get_signed_area(){ T ret = 0.0; for(int i=1;i tri(V[0],V[i],V[i+1]); ret += tri.get_signed_area(); } return ret; } T get_area(){ return abs(get_signed_area()); } T get_diameter(){ vector dis(V.size()); int now = 0; for(int i=0;i P){ for(int i=0;i l(V[i],V[(i+1)%V.size()]); if(l.get_dis(P) P){ if(is_on_side(P))return true; long double R = 0.0; for(int i=0;i p1(V[i]-P),p2(V[(i+1)%V.size()]-P); R += p1.angle_difference(p2); } return abs(R)>=eps; } }; template struct circle{ vector_2d C; T R; circle(vector_2d c=vector_2d(),T r=0.0){ C = c; R = r; } vector> get_cross_point(circle C2){ vector> ret; T d = C.get_dis(C2.C); if(d>R+C2.R+eps)return ret; if(d+eps e1 = (C2.C-C); e1.update_rad(1.0/d,0.0); vector_2d e2 = e1; e2.update_dir(1.0,acos(-1.0)/2.0); e1.update_rad(Rc,0.0); e2.update_rad(Rs,0.0); ret.push_back(C + e1+e2); e2.update_dir(1.0,-acos(-1.0)); ret.push_back(C+e1+e2); return ret; } }; vector get_CH(vector> &v){ vector,int>> V(v.size()); for(int i=0;ieps)return a.first.y ret; for(int i=0;i v1 = V[ret[ret.size()-2]].first,v2 = V[ret[ret.size()-1]].first,v3 = V[i].first; v3 -= v2; v2 -= v1; if(v2.get_cross_product(v3)>-eps){ ret.push_back(i); } else{ ret.pop_back(); i--; continue; } } } for(int i=(int)V.size()-2;i>=0;i--){ if(ret.size()<2){ ret.push_back(i); } else{ vector_2d v1 = V[ret[ret.size()-2]].first,v2 = V[ret[ret.size()-1]].first,v3 = V[i].first; v3 -= v2; v2 -= v1; if(v2.get_cross_product(v3)>-eps){ ret.push_back(i); } else{ ret.pop_back(); i++; continue; } } } ret.pop_back(); for(int i=0;i S; { vector ret2; for(int i=0;i>N; vector> xy(N); rep(i,N){ cin>>xy[i].first>>xy[i].second; } sort(xy.begin(),xy.end()); dsu D(N); rep(i,N){ int x = xy[i].first,y = xy[i].second; rep(j,11){ for(int k=-10;k<=10;k++){ if(j*j + k*k <= 100){ int d = distance(xy.begin(),lower_bound(xy.begin(),xy.end(),make_pair(x+j,y+k))); if(d!=N && xy[d]==make_pair(x+j,y+k))D.merge(d,i); } } } } long double ans = 1.0; auto g = D.groups(); rep(i,g.size()){ if(g[i].size()==1){ ans = max(ans,(long double)2.0); continue; } vector> temp; rep(j,g[i].size()){ temp.push_back(vector_2d(xy[g[i][j]].first,xy[g[i][j]].second)); } auto ret = get_CH(temp); vector> temp2; rep(j,ret.size()){ temp2.push_back(temp[ret[j]]); } polygon P(temp); ans = max(ans,P.get_diameter()+2.0); } cout<